Belajar Algoritm - Quick Sort, Heap Sort & Non-Comparison Sorts

#Pendahuluan

Setelah di episode 4 kita membahas Insertion, Selection, dan Merge Sort, pada episode ini kita melengkapi arsenal sorting dengan tiga algoritma lagi: Quick Sort yang paling banyak dipakai di praktik, Heap Sort yang menggabungkan O(n log n) dengan in-place, dan Non-Comparison Sorts yang mematahkan batasan Ω(n log n) untuk input yang constrained.

Quick Sort menjadi favorit karena rata-rata O(n log n) dengan overhead memori minimal. Heap Sort memberikan jaminan O(n log n) worst-case secara in-place. Non-comparison sorts membuktikan bahwa batasan Ω(n log n) hanya berlaku untuk comparison-based sorting.

#Quick Sort

Quick Sort memilih sebuah elemen sebagai pivot, mempartisi array menjadi dua bagian (elemen lebih kecil di kiri, lebih besar di kanan), lalu secara rekursif mengurutkan masing-masing bagian.

python

import random
 
def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    return arr
 
def partition(arr, low, high):
    # Random pivot untuk menghindari worst case
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

#Analisis Kompleksitas

Metrik	Nilai
Best case	Θ(n log n) — pivot selalu tengah
Average case	Θ(n log n) — random pivot
Worst case	O(n²) — array sudah terurut tanpa random
Space	O(log n) — stack rekursi
Stability	Tidak — partition menukar elemen

Warning

Quick Sort tanpa random pivot memiliki worst case O(n²) pada array yang sudah terurut — karena pivot selalu elemen ekstrem. Random pivot mengubah ini menjadi probabilistik: kemungkinan mendapat worst case sangat kecil secara matematis.

#Heap Sort

Heap Sort memanfaatkan max-heap — struktur data pohon biner di mana parent selalu lebih besar dari children. Prosesnya: build max-heap dari array, lalu menukar root (elemen terbesar) dengan elemen terakhir, kurangi heap size, dan heapify root.

python

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
 
def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

#Analisis Kompleksitas

Metrik	Nilai
Worst case	O(n log n)
Best case	Θ(n log n) — tetap membangun heap
Space	O(1) — in-place
Stability	Tidak

Heap Sort menarik karena O(n log n) worst-case secara in-place — tidak ada stack rekursi seperti Quick Sort, tidak ada array temporer seperti Merge Sort. Kekurangannya: cache performance lebih buruk dari Quick Sort karena akses memori tidak sequential.

#Non-Comparison Sorts

Batasan Ω(n log n) hanya berlaku untuk comparison-based sorting — algoritma yang menentukan urutan hanya berdasarkan perbandingan pasangan elemen. Jika kita bisa mengekstrak informasi dari elemen itu sendiri (misal angka dalam range terbatas), kita bisa mencapai O(n).

#Counting Sort

Menghitung frekuensi setiap nilai, lalu menempatkan elemen berdasarkan kumulatif frekuensi.

python

def counting_sort(arr, k):
    """arr: array non-negatif, k: max value"""
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1
    result = []
    for i in range(k + 1):
        result.extend([i] * count[i])
    return result

Time: O(n + k), Space: O(k). Efektif jika k ≈ n.

#Radix Sort

Mengurutkan digit per digit, dari yang paling tidak signifikan ke yang paling signifikan, menggunakan stable sort (counting sort) sebagai subroutine.

Time: O(d × (n + b)) di mana d = jumlah digit, b = basis. Untuk angka dalam range tetap, ini efektif O(n).

#Bucket Sort

Mendistribusikan elemen ke bucket-bucket, mengurutkan setiap bucket secara individual, lalu menggabungkan. Efektif untuk input yang terdistribusi merata.

Time: O(n) average untuk distribusi merata, O(n²) worst case.

#Bandingkan: Quick Sort vs Merge Sort vs Heap Sort

Kriteria	Quick Sort	Merge Sort	Heap Sort
Average time	Θ(n log n)	Θ(n log n)	Θ(n log n)
Worst case	O(n²)	O(n log n)	O(n log n)
Space	O(log n)	O(n)	O(1)
Cache performance	Excellent	Fair	Poor
Stability	Tidak	Ya	Tidak
Digunakan di	C stdlib, Java Arrays.sort (primitif)	Python TimSort, Java Arrays.sort (object)	Basis Heap Priority Queue

Note

Quick Sort menang di cache performance — ia mengakses memori secara sequential saat partitioning, sehingga CPU cache hit rate tinggi. Inilah mengapa meskipun O(n²) worst-case, Quick Sort masih menjadi pilihan default di banyak stdlib.

#Praktik

Implementasi ketiganya dan benchmark dengan dataset 100, 1000, 10000 elemen. Bandingkan waktu aktual dengan teori. Perhatikan bahwa Quick Sort (dengan random pivot) secara average hampir selalu menang, tetapi Merge Sort memberikan jaminan konsisten.

#Penutup

Pada episode 5 ini, kalian telah memahami:

Quick Sort: O(n log n) average dengan random pivot, cache-friendly, tetapi O(n²) worst-case.
Heap Sort: O(n log n) in-place, tetapi cache-unfriendly.
Non-comparison sorts: O(n) untuk input constrained — mematahkan Ω(n log n) karena tidak berbasis perbandingan.
Pilihan sorting di stdlib didasarkan pada trade-off ini.

Di episode 6 selanjutnya kita akan membahas stability, in-place, dan external sorting — konsep lanjutan yang menentukan kapan sebuah sorting bisa dipakai di production (misal sorting dataset yang lebih besar dari RAM). Sampai jumpa di episode 6!