Python Sorting in Practice

"""Topic  : sorted() vs list.sort() basics
Time   : O(n log n)  Timsort
Space  : O(n) for sorted(), O(1) extra for .sort()"""

from dataclasses import dataclass, field


# ── sorted() vs list.sort() ───────────────────────────────────────────────────

def demo_sorted_vs_sort() -> None:
    """Demonstration of the key differences between the two functions."""
    original = [3, 1, 4, 1, 5, 9, 2, 6]

    #sorted(): returns a new list, original unchanged
    new_list = sorted(original)
    print(f"sorted() return: {new_list}")
    print(f"Original unchanged: {original}")

    #list.sort(): in-place, returns None
    copy = original[:]
    ret = copy.sort()
    print(f"sort() return value: {ret}     ← None!")
    print(f"Copy modified: {copy}")

    #Common mistakes
    mistake = [3, 1, 2]
    mistake.sort()           #Correct usage
    print(f"Correct sort: {mistake}")

    oops = sorted([3, 1, 2])
    print(f"Using return value: {oops}     ← This is how it should be used")


#── String sorting ───────────────────────────────────────────────────────────────

def demo_string_sort() -> None:
    """Various examples of string sorting."""
    words = ["banana", "Apple", "cherry", "date", "fig"]

    print("=== String sorting ===")
    print(f"Default (dictionary order, case-sensitive): {sorted(words)}")
    print(f"Ignore case                : {sorted(words, key=str.lower)}")
    print(f"By length                  : {sorted(words, key=len)}")
    print(f"By reverse length          : {sorted(words, key=len, reverse=True)}")
    print(f"Order by last letter           : {sorted(words, key=lambda w: w[-1])}")

    #Be careful with numeric strings
    num_strs = ["10", "9", "100", "2", "20"]
    print(f"\nNumber strings in dictionary order  : {sorted(num_strs)}")
    print(f"Number strings in numeric order     : {sorted(num_strs, key=int)}")


#── Number sorting ───────────────────────────────────────────────────────────────

def demo_number_sort() -> None:
    """Various examples of number sorting."""
    nums = [-5, 3, -1, 4, -9, 2]

    print("\n=== Number Sorting ===")
    print(f"Ascending order      : {sorted(nums)}")
    print(f"Descending order     : {sorted(nums, reverse=True)}")
    print(f"By absolute value    : {sorted(nums, key=abs)}")
    print(f"By square            : {sorted(nums, key=lambda x: x**2)}")


#── Custom object sorting ─────────────────────────────────────────────────────────

@dataclass
class Student:
    name: str
    score: int
    grade: str

    def __repr__(self) -> str:
        return f"Student({self.name}, {self.score}, {self.grade})"


def demo_object_sort() -> None:
    """Object Sorting."""
    students = [
        Student("Hong Gil-dong", 85, "A"),
        Student("Yi Sun-sin", 92, "B"),
        Student("Gang Gam-chan", 85, "A"),
        Student("Yu Gwan-sun", 78, "B"),
    ]

    print("\n=== Object Sorting ===")
    by_score = sorted(students, key=lambda s: s.score)
    print(f"Score ascending     : {by_score}")

    by_score_desc = sorted(students, key=lambda s: -s.score)
    print(f"Score descending    : {by_score_desc}")

    by_name = sorted(students, key=lambda s: s.name)
    print(f"Name order          : {by_name}")

    #Using attrgetter
    from operator import attrgetter
    by_grade_score = sorted(students, key=attrgetter('grade', 'score'))
    print(f"Class → Score order : {by_grade_score}")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    demo_sorted_vs_sort()
    demo_string_sort()
    demo_number_sort()
    demo_object_sort()

"""Topic  : Using key functions — lambda, len, itemgetter, multiple fields
Time   : O(n log n)  Timsort
Space  : O(n)"""

from operator import itemgetter, attrgetter


#── Basics of lambda ───────────────────────────────────────────────────────────────

def demo_lambda_key() -> None:
    """Various patterns using lambda as a key."""
    print("=== Using lambda key ===")

    #Specific index of a tuple
    coords = [(3, 4), (1, 2), (5, 0), (2, 8)]
    print(f"By x-coordinate: {sorted(coords, key=lambda p: p[0])}")
    print(f"By y-coordinate: {sorted(coords, key=lambda p: p[1])}")

    #By distance (from origin)
    print(f"By distance: {sorted(coords, key=lambda p: p[0]**2 + p[1]**2)}")

    #List of dictionaries
    people = [
        {"name": "Hong Gil-dong", "age": 30},
        {"name": "Yi Sun-sin", "age": 25},
        {"name": "Gang Gam-chan", "age": 35},
    ]
    print(f"By age: {sorted(people, key=lambda p: p['age'])}")
    print(f"By name: {sorted(people, key=lambda p: p['name'])}")


#── Built-in function key ──────────────────────────────────────────────────────────

def demo_builtin_key() -> None:
    """Use a built-in function as a key."""
    print("=== Built-in function key ===")

    words = ["python", "is", "awesome", "and", "fast"]
    print(f"Length order (len)  : {sorted(words, key=len)}")
    print(f"Absolute value (abs)   : {sorted([-3, 1, -5, 2, -1], key=abs)}")
    print(f"Lowercase (lower) : {sorted(['Banana', 'apple', 'Cherry'], key=str.lower)}")

    #Convert to str
    mixed_nums = [100, 9, 20, 3, 50]
    print(f"Numbers → Lexical order   : {sorted(mixed_nums, key=str)}")
    print(f"Numbers → Numerical order   : {sorted(mixed_nums)}")


# ── operator.itemgetter ───────────────────────────────────────────────────────

def demo_itemgetter() -> None:
    """itemgetter: faster and more concise than lambda."""
    print("\n=== operator.itemgetter ===")

    data = [("Alice", 85, "Class A"), ("Bob", 92, "Class B"),
            ("Charlie", 85, "Class A"), ("Dave", 78, "Class B")]

    #Single index
    print(f"Name order   : {sorted(data, key=itemgetter(0))}")
    print(f"Score order   : {sorted(data, key=itemgetter(1))}")

    #Multiple indices — compare with tuple
    print(f"Class → Score order: {sorted(data, key=itemgetter(2, 1))}")

    #Use in list of dictionaries
    products = [
        {"name": "Apple", "price": 1200, "qty": 50},
        {"name": "Pear", "price": 2500, "qty": 30},
        {"name": "Persimmon", "price": 800, "qty": 70},
    ]
    print(f"Price order: {sorted(products, key=itemgetter('price'))}")
    print(f"Quantity order: {sorted(products, key=itemgetter('qty'))}")


#── Composite key pattern ─────────────────────────────────────────────────────────

def demo_complex_key() -> None:
    """A complex key pattern frequently used in practice."""
    print("=== Composite key pattern ===")

    #Descending by score + ascending by name (negative trick)
    students = [("Hong Gil-dong", 85), ("Yi Sun-sin", 92), ("Gang Gam-chan", 85), ("Yu Gwan-sun", 92)]
    result = sorted(students, key=lambda s: (-s[1], s[0]))
    print(f"Score↓ Name↑: {result}")

    #Ascending by string length + lexicographical order
    words = ["cat", "at", "dog", "be", "ant"]
    result2 = sorted(words, key=lambda w: (len(w), w))
    print(f"Length↑ Lexical↑: {result2}")

    #Special case: sorting with None included
    data_with_none = [3, None, 1, None, 2]
    result3 = sorted(data_with_none, key=lambda x: (x is None, x or 0))
    print(f"None last : {result3}")


# ── attrgetter ────────────────────────────────────────────────────────────────

def demo_attrgetter() -> None:
    """attrgetter: Sorting based on object attributes."""
    from dataclasses import dataclass

    @dataclass
    class Point:
        x: int
        y: int
        label: str

        def __repr__(self) -> str:
            return f"({self.x},{self.y},{self.label})"

    points = [Point(3, 4, "C"), Point(1, 2, "A"), Point(3, 1, "B")]

    print("\n=== attrgetter ===")
    print(f"x order          : {sorted(points, key=attrgetter('x'))}")
    print(f"x→y order         : {sorted(points, key=attrgetter('x', 'y'))}")
    print(f"label order       : {sorted(points, key=attrgetter('label'))}")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    demo_lambda_key()
    demo_builtin_key()
    demo_itemgetter()
    demo_complex_key()
    demo_attrgetter()

"""Topic  : Multi-criteria sorting — Name → Age, Tuple Comparison
Time   : O(n log n)
Space  : O(n)"""


#── Multi-Criteria Sorting Patterns ───────────────────────────────────────────────

def demo_multi_key_patterns() -> None:
    """Practical patterns for multi-criteria sorting."""
    print("=== Multi-Criteria Sorting Patterns ===")

    employees = [
        ("Kim Cheolsu", "Development Team", 5_000_000),
        ("Lee Younghee", "Marketing", 4_500_000),
        ("Park Minjun", "Development Team", 4_500_000),
        ("Choi Jisoo", "Marketing", 5_000_000),
        ("Jung Daeun", "Development Team", 6_000_000),
    ]

    #By team, if it's the same team, by descending salary
    by_dept_salary = sorted(
        employees,
        key=lambda e: (e[1], -e[2])
    )
    print("By team, salary in descending order within team:")
    for emp in by_dept_salary:
        print(f"{emp[1]:10s} | {emp[0]} | {emp[2]:,} KRW")

    #By descending salary, if equal then by ascending name
    by_salary_name = sorted(
        employees,
        key=lambda e: (-e[2], e[0])
    )
    print("Salary descending, name ascending:")
    for emp in by_salary_name:
        print(f"{emp[0]} | {emp[2]:,} KRW")


#── Principle of Tuple Comparison ────────────────────────────────────────────────

def demo_tuple_comparison() -> None:
    """Python tuple comparison is the basis for multi-criteria sorting."""
    print("=== Principle of tuple comparison ===")

    pairs = [(1, 2), (1, 1), (2, 0), (1, 3)]
    print(f"Original      : {pairs}")
    print(f"After sorting: {sorted(pairs)}")
    print("→ (1,1) < (1,2) < (1,3) < (2,0)  If the first element is the same, compare the second")

    #Coding Test Practice: by starting point ascending, by ending point descending
    intervals = [(1, 5), (1, 3), (2, 4), (1, 7)]
    sorted_intervals = sorted(intervals, key=lambda x: (x[0], -x[1]))
    print(f"Interval sorting: {intervals}")
    print(f"Start↑ End↓   : {sorted_intervals}")


#── Name Sorting (Baekjoon Style) ───────────────────────────────────────────────

def demo_name_length_sort() -> None:
    """Baekjoon 1181 style: Ascending by length, and if the same, in lexicographical order."""
    words = ["zoo", "a", "bc", "ab", "b", "aaa", "z"]
    result = sorted(set(words), key=lambda w: (len(w), w))
    print(f"=== Name sorting (Baekjoon 1181 style) ===")
    print(f"Input: {words}")
    print(f"Remove duplicates + length↑ dictionary↑: {result}")


#── Coordinate Sorting (Baekjoon Style) ───────────────────────────────────────────

def demo_coordinate_sort() -> None:
    """Baekjoon 11650 style: x in ascending order, if equal then y in ascending order."""
    coords = [(3, 4), (1, 1), (1, -1), (2, 2), (3, 3)]
    result = sorted(coords)          #OK with basic tuple comparison
    print(f"=== Coordinate sorting (Baekjoon 11650 style) ===")
    print(f"Input  : {coords}")
    print(f"Sorted : {result}")

    #When written explicitly
    result2 = sorted(coords, key=lambda p: (p[0], p[1]))
    assert result == result2
    print("← sorted by x→y")


#── Multi-Level Sorting Using Stable Sort ─────────────────────────────────────────

def demo_stable_multi_sort() -> None:
    """Sequential sorting by priority using stable sort (classical technique)."""
    print("=== Stable sort multi-level sorting ===")

    data = [
        ("Alice", 85, "Class B"),
        ("Bob", 92, "Class A"),
        ("Charlie", 85, "Class A"),
        ("Dave", 78, "Class A"),
    ]

    #Goal: Class A → Class B, if the same class then descending score, if same score then by name
    #Method 1: Composite key (recommended)
    result1 = sorted(data, key=lambda x: (x[2], -x[1], x[0]))
    print("Composite key sorting:")
    for r in result1:
        print(f"  {r}")

    #Method 2: Consecutive application of stable sort (from lower priority → higher priority)
    step1 = sorted(data, key=lambda x: x[0])           #Name
    step2 = sorted(step1, key=lambda x: -x[1])          #Score descending
    step3 = sorted(step2, key=lambda x: x[2])           #Class

    print("Multi-level stable sorting:")
    for r in step3:
        print(f"  {r}")

    assert result1 == step3, "The results of the two methods are different!"
    print("Both methods yield the same result: ✓")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    demo_multi_key_patterns()
    demo_tuple_comparison()
    demo_name_length_sort()
    demo_coordinate_sort()
    demo_stable_multi_sort()

"""Topic: Sorting Applications — Coordinate Compression, Duplicate Removal, Top-K
Time: O(n log n) for sorting, O(n) for compression/duplicate removal
Space: O(n)"""


#── Coordinate Compression ─────────────────────────────────────────────────────────

def coordinate_compression(arr: list[int]) -> list[int]:
    """Coordinate Compression.

    When the range of values is very large (e.g., 0~10⁹), convert to indices (0~n-1).
    Refer to Baekjoon 18870.

    Args:
        arr: The original array to compress
    Returns:
        The compressed 0-indexed array"""
    #Remove duplicates and sort → Map to ranks
    rank = {v: i for i, v in enumerate(sorted(set(arr)))}
    return [rank[v] for v in arr]


def demo_coordinate_compression() -> None:
    """Example of coordinate compression."""
    print("=== Coordinate Compression ===")
    examples = [
        [5, 4, 2, 3, 1],
        [100, 50, 200, 50, 100],
        [1_000_000, 1, 500_000, 1, 1_000_000],
    ]
    for arr in examples:
        compressed = coordinate_compression(arr)
        print(f"Original: {arr}")
        print(f"Compressed: {compressed}")
        print()


#── Deduplication Based on Sorting ────────────────────────────────────────────────

def deduplicate_sorted(arr: list[int]) -> list[int]:
    """Remove duplicates by sorting and then comparing adjacent elements (O(n log n))."""
    if not arr:
        return []
    a = sorted(arr)
    result = [a[0]]
    for i in range(1, len(a)):
        if a[i] != a[i - 1]:
            result.append(a[i])
    return result


def demo_deduplication() -> None:
    """Comparison of duplicate removal methods."""
    print("=== Deduplication ===")
    data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

    #Method 1: set (order not important)
    by_set = sorted(set(data))

    #Method 2: Compare adjacent after sorting (when order preservation is not required)
    by_sort = deduplicate_sorted(data)

    #Method 3: Deduplication preserving order
    seen: set[int] = set()
    order_preserved = [x for x in data if not (seen.add(x) or x in seen)]  # type: ignore

    print(f"Original      : {data}")
    print(f"Using set     : {by_set}")
    print(f"Sort comparison: {by_sort}")
    assert by_set == by_sort


#── Top-K Elements ──────────────────────────────────────────────────────────────

def top_k_sort(arr: list[int], k: int) -> list[int]:
    """Top-K extraction by sorting O(n log n)."""
    return sorted(arr, reverse=True)[:k]


def top_k_heap(arr: list[int], k: int) -> list[int]:
    """Extract Top-K with heapq.nlargest O(n log k)."""
    import heapq
    return heapq.nlargest(k, arr)


def demo_top_k() -> None:
    """Top-K extraction comparison."""
    print("\n=== Top-K Extraction ===")
    scores = [85, 92, 78, 96, 88, 74, 100, 65, 91, 83]
    k = 3

    by_sort = top_k_sort(scores, k)
    by_heap = top_k_heap(scores, k)

    print(f"Scores: {scores}")
    print(f"Top-{k} (sorted): {by_sort}")
    print(f"Top-{k} (heap)  : {by_heap}")

    #Top K indices
    indexed = sorted(enumerate(scores), key=lambda x: -x[1])[:k]
    print(f"Top-{k} indices: {[i for i, _ in indexed]}")


#── Sorting-Based Greedy Algorithm ──────────────────────────────────────────────

def interval_scheduling(intervals: list[tuple[int, int]]) -> int:
    """Activity selection problem (Greedy sorted by finish time ascending).

    Return the maximum number of non-overlapping activities."""
    #Sort by end time in ascending order
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    count = 0
    last_end = -1
    for start, end in sorted_intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count


def demo_greedy() -> None:
    """Example of sorting-based greedy."""
    print("\n=== Sorting-Based Greedy (Activity Selection) ===")
    activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9),
                  (5, 9), (6, 10), (8, 11), (8, 12), (2, 14)]
    max_activities = interval_scheduling(activities)
    print(f"Activity List: {activities}")
    print(f"Maximum Number of Non-Overlapping Activities: {max_activities}")


#── Main ────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    demo_coordinate_compression()
    demo_deduplication()
    demo_top_k()
    demo_greedy()

    #Accuracy Verification
    assert coordinate_compression([5, 4, 2, 3, 1]) == [4, 3, 1, 2, 0]
    assert coordinate_compression([100, 50, 200, 50, 100]) == [1, 0, 2, 0, 1]
    print("Coordinate Compression Accuracy Check: PASS")