Sorting Problems — Complete Guide

Sorting Problems — Complete Guide

· 22분 읽기 · 수정 Beginner Tutorial
Sorting Problems — Complete Guide

이 글의 핵심

Master sorting problems for coding interviews. Learn Python sort(), custom sorting with key functions, and multi-condition sorting patterns.

Introduction

In coding interviews, sorting is often the first step to solving problems. Whether organizing candidates by score/time, or preparing for greedy/binary search algorithms, sort and key functions express conditions elegantly.

1. Basic Sorting

Python Sorting

Choose between in-place sorting (sort) or creating a new list (sorted) based on whether you need to preserve the original.

# Ascending order
arr = [5, 2, 8, 1, 9]
arr.sort()
print(arr)  # [1, 2, 5, 8, 9]
# Descending order
arr.sort(reverse=True)
print(arr)  # [9, 8, 5, 2, 1]
# Return new list
arr = [5, 2, 8, 1, 9]
sorted_arr = sorted(arr)
print(arr)  # [5, 2, 8, 1, 9] (original preserved)
print(sorted_arr)  # [1, 2, 5, 8, 9]

Time Complexity

  • sort(), sorted(): O(n log n) (Timsort)
  • Stable sorting guaranteed

2. Custom Sorting

Key Functions

# Sort by absolute value
arr = [-5, -2, 1, 3, -8]
arr.sort(key=abs)
print(arr)  # [1, -2, 3, -5, -8]
# Sort by string length
words = ["apple", "pie", "banana"]
words.sort(key=len)
print(words)  # ["pie", "apple", "banana"]
# Sort tuples (by first element)
students = [(85, "Alice"), (90, "Bob"), (80, "Charlie")]
students.sort()
print(students)
# [(80, 'Charlie'), (85, 'Alice'), (90, 'Bob')]

Multi-Condition Sorting

# Score descending, name ascending
students = [
    ("Alice", 85),
    ("Bob", 90),
    ("Charlie", 85),
    ("David", 90)
]
students.sort(key=lambda x: (-x[1], x[0]))
print(students)
# [('Bob', 90), ('David', 90), ('Alice', 85), ('Charlie', 85)]
# Age ascending, name descending
people = [
    ("Alice", 30),
    ("Bob", 25),
    ("Charlie", 30),
]
people.sort(key=lambda x: (x[1], -ord(x[0][0])))

cmp_to_key

from functools import cmp_to_key
def compare(x, y):
    if x > y:
        return 1
    elif x < y:
        return -1
    else:
        return 0
arr = [5, 2, 8, 1]
arr.sort(key=cmp_to_key(compare))
print(arr)  # [1, 2, 5, 8]

3. Problem Solving

Problem 1: Largest Number

def largest_number(nums):
    """
    Concatenate numbers to form largest number
    [3, 30, 34, 5, 9] → "9534330"
    """
    from functools import cmp_to_key
    
    def compare(x, y):
        if x + y > y + x:
            return -1
        elif x + y < y + x:
            return 1
        else:
            return 0
    
    nums_str = list(map(str, nums))
    nums_str.sort(key=cmp_to_key(compare))
    
    result = '.join(nums_str)
    return '0' if result[0] == '0' else result
print(largest_number([3, 30, 34, 5, 9]))  # "9534330"
print(largest_number([0, 0, 0]))  # "0"

Problem 2: H-Index

def h_index(citations):
    """
    Find h-index: h papers cited at least h times
    [3, 0, 6, 1, 5] → 3
    """
    citations.sort(reverse=True)
    
    h = 0
    for i, citation in enumerate(citations):
        if citation >= i + 1:
            h = i + 1
        else:
            break
    
    return h
print(h_index([3, 0, 6, 1, 5]))  # 3
print(h_index([10, 8, 5, 4, 3]))  # 4

Problem 3: Merge Intervals

def merge_intervals(intervals):
    """
    Merge overlapping intervals
    [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
    """
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        if current[0] <= last[1]:
            merged[-1] = [last[0], max(last[1], current[1])]
        else:
            merged.append(current)
    
    return merged
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(intervals))
# [[1, 6], [8, 10], [15, 18]]

Problem 4: Meeting Rooms

def max_meetings(meetings):
    """
    Maximum non-overlapping meetings
    [(1, 4), (3, 5), (0, 6), (5, 7)] → 3
    """
    meetings.sort(key=lambda x: x[1])  # Sort by end time
    
    count = 0
    last_end = 0
    
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    
    return count
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings))  # 4

4. Sorting Patterns

Pattern 1: Sort + Two Pointers

def two_sum_sorted(arr, target):
    """
    Sort then use two pointers to find sum
    """
    arr.sort()
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [arr[left], arr[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return None
print(two_sum_sorted([2, 7, 11, 15], 9))  # [2, 7]

Pattern 2: Sort + Binary Search

from bisect import bisect_left
def count_smaller(arr, target):
    """
    Sort then binary search
    """
    arr.sort()
    idx = bisect_left(arr, target)
    return idx
arr = [5, 2, 8, 1, 9]
print(count_smaller(arr, 6))  # 3 (1, 2, 5)

Pattern 3: Sort + Greedy

def assign_cookies(children, cookies):
    """
    Assign cookies to children (maximize satisfaction)
    """
    children.sort()
    cookies.sort()
    
    i = j = 0
    while i < len(children) and j < len(cookies):
        if cookies[j] >= children[i]:
            i += 1
        j += 1
    
    return i
children = [1, 2, 3]
cookies = [1, 1]
print(assign_cookies(children, cookies))  # 1

Pattern 4: Custom Comparator

from functools import cmp_to_key
def sort_by_custom_rule(arr):
    """
    Sort with custom comparison logic
    """
    def compare(x, y):
        # Custom logic here
        if some_condition(x, y):
            return -1
        elif other_condition(x, y):
            return 1
        else:
            return 0
    
    arr.sort(key=cmp_to_key(compare))
    return arr

5. Practical Tips

Sorting Debugging

def debug_sort(arr, key=None):
    """Print sorting process"""
    print("Original:", arr)
    sorted_arr = sorted(arr, key=key)
    print("Sorted:", sorted_arr)
    return sorted_arr
students = [("Alice", 85), ("Bob", 90), ("Charlie", 80)]
debug_sort(students, key=lambda x: x[1])

Performance Measurement

import time
arr = list(range(100000, 0, -1))
start = time.time()
arr.sort()
end = time.time()
print(f"Sort time: {(end - start) * 1000:.2f}ms")

Common Mistakes

# ❌ Wrong: Modifying while iterating
arr = [3, 1, 4, 1, 5]
# for i, val in enumerate(arr):
#     if val == 1:
#         arr.remove(val)  # Skips elements!
# ✅ Correct: Filter with list comprehension
arr = [x for x in arr if x != 1]
# ❌ Wrong: Sorting without key
words = ["apple", "Banana", "cherry"]
words.sort()  # ['Banana', 'apple', 'cherry'] (uppercase first)
# ✅ Correct: Case-insensitive
words.sort(key=str.lower)  # ['apple', 'Banana', 'cherry']

Summary

Key Points

  1. Python Sorting: sort(), sorted(), key functions
  2. Custom Sorting: lambda, cmp_to_key
  3. Multi-Condition: Return tuple (condition1, condition2)
  4. Usage Patterns: Two pointers, binary search, greedy
  5. Time Complexity: O(n log n)

When to Sort

Problem TypeApproachReason
Find pairsSort + Two PointersO(n) after sort
Range queriesSort + Binary SearchO(log n) search
Interval problemsSort by start/endGreedy selection
Frequency problemsSort by countTop-k elements

Beginner

  • LeetCode 88: Merge Sorted Array
  • LeetCode 242: Valid Anagram
  • LeetCode 349: Intersection of Two Arrays

Intermediate

  • LeetCode 56: Merge Intervals
  • LeetCode 75: Sort Colors
  • LeetCode 148: Sort List

Advanced

  • LeetCode 315: Count of Smaller Numbers After Self
  • LeetCode 327: Count of Range Sum
  • LeetCode 493: Reverse Pairs

Keywords

Sorting, Algorithm, Python sort, Custom Sorting, Key Function, Multi-Condition Sort, Coding Interview, Problem Solving, Time Complexity, Stable Sort

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Master sorting problems for coding interviews. Learn Python sort(), custom sorting with key functions, and multi-conditi…

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

Other articles related to this topic.

Keywords Covered in This Article (Related Search Terms)

This article covers Algorithm, Sorting, Problem Solving, Coding Interview, Python, sort.