Belajar Algoritm - Lower Bound & Sorting Applications

#Pendahuluan

Setelah di episode 6 kita memahami stability, in-place, dan external sorting, pada episode ini kita menutup FASE 2: SORTING dengan dua topik penting: lower bound Ω(n log n) untuk comparison-based sorting, dan aplikasi sorting yang melampaui sekadar mengurutkan array.

Mengapa lower bound penting? Karena ia menjawab pertanyaan fundamental: "bisakah kita mengurutkan lebih cepat dari O(n log n)?" Jawabannya: tidak, jika kita hanya menggunakan perbandingan. Ini membuktikan bahwa Merge Sort dan Heap Sort sudah optimal untuk comparison-based sorting, dan membuka jalan untuk non-comparison sorts (episode 5) yang mematahkan batasan ini.

#Lower Bound Ω(n log n): Decision Tree Argument

Setiap comparison-based sorting bisa dimodelkan sebagai decision tree — pohon biner di mana setiap internal node adalah perbandingan arr[i] ≤ arr[j], dan setiap leaf adalah satu kemungkinan urutan output.

Untuk n elemen, ada n! kemungkinan urutan. Decision tree harus punya setidaknya n! leaf untuk bisa menghasilkan semua urutan. Pohon biner dengan n! leaf memiliki kedalaman minimal log₂(n!).

Menggunakan Stirling's approximation: log₂(n!) = Θ(n log n). Oleh karena itu, setiap comparison-based sorting membutuhkan Ω(n log n) perbandingan di worst case.

#Aplikasi 1: Counting Inversions

Inversion adalah pasang (i, j) di mana i < j tetapi arr[i] > arr[j]. Jumlah inversions mengukur seberapa jauh array dari kondisi terurut — 0 inversions berarti sudah terurut.

Brute force: O(n²) — cek semua pasang. Optimasi: modifikasi merge sort.

Saat merge, ketika elemen kanan (arr[j]) lebih kecil dari elemen kiri (arr[i]), maka seluruh sisa elemen kiri (dari i sampai mid) juga merupakan inversion dengan arr[j]. Kita bisa menghitung ini tanpa nested loop.

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, left_inv = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])
    merged, split_inv = merge_count(left, right)
    return merged, left_inv + right_inv + split_inv
 
def merge_count(left, right):
    result = []
    inversions = 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            inversions += len(left) - i
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, inversions

Time: Θ(n log n) — sama dengan merge sort, ditambah O(n) untuk merge. Ini jauh lebih cepat dari brute force O(n²).

#Aplikasi 2: Closest Pair of Points

Closest pair adalah pasang titik dengan jarak Euclidean terkecil. Brute force: O(n²). Dengan divide & conquer: O(n log n).

Strateginya: bagi titik menjadi dua setengah berdasarkan koordinat x, cari closest pair di masing-masing setengah secara rekursif, lalu periksa titik-titik di strip tengah (jarak dari garis pembagi kurang dari δ, jarak minimum rekursif). Strip hanya perlu memeriksa maksimal 7 titik berikutnya per titik → O(n) untuk strip.

#Aplikasi 3: Median Streaming

Median streaming adalah menemukan median dari data yang terus bertambah — misal median dari seluruh angka yang sudah dilihat sejauh ini.

Solusi: gunakan max-heap untuk separuh lebih kecil dan min-heap untuk separuh lebih besar. Heap balancing memastikan median selalu ada di salah satu root heap.

• Insert: O(log n)
• Get median: O(1)
• Space: O(n)

Ini lebih efektif dari sorting ulang setiap kali (O(n log n) per insert) atau brute force (O(n) per median query).

#Penutup

Pada episode 7 ini, kalian telah memahami:

• Lower bound Ω(n log n) terbukti via decision tree — comparison-based sorting sudah optimal di Θ(n log n).
• Counting inversions dimodifikasi dari merge sort: Θ(n log n) vs brute force O(n²).
• Closest pair dengan divide & conquer: O(n log n) vs brute force O(n²).
• Median streaming dengan dual heap: O(log n) insert, O(1) query.

Ini menutup FASE 2: SORTING. Di episode 8 selanjutnya kita masuk ke FASE 3: SEARCHING & DIVIDE & CONQUER — membahas Binary Search dan Variannya: first/last occurrence, lower/upper bound, search in rotated array, dan answer binary search. Sampai jumpa di episode 8!