Belajar Algoritm - Sorting Dasar: Insertion, Selection & Merge Sort

#Pendahuluan

Setelah di episode 3 kita memahami enam paradigma desain algoritma, pada episode ini kita mulai FASE 2: SORTING dengan tiga algoritma paling fundamental. Sorting adalah salah satu masalah paling dipelajari di ilmu komputer — bukan hanya karena relevansinya di dunia nyata, tetapi karena ia mengajarkan perbandingan trade-off yang menjadi inti dari analisis algoritma.

Menguasai Insertion Sort, Selection Sort, dan Merge Sort memberikan fondasi untuk memahami algoritma sorting yang lebih kompleks di episode berikutnya. Kita akan melihat bagaimana paradigma yang berbeda — brute force vs divide & conquer — menghasilkan kompleksitas waktu yang sangat berbeda.

#Insertion Sort

Insertion Sort bekerja seperti cara kalian mengurutkan kartu di tangan: ambil satu elemen dari unsorted section, lalu sisipkan ke posisi yang benar di sorted section.

python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

#Analisis Kompleksitas

Metrik	Nilai
Worst case	O(n²) — array terbalik
Best case	Θ(n) — array sudah terurut
Rata-rata	Θ(n²) — input acak
Space	O(1) — in-place
Stability	Ya — elemen equal mempertahankan urutan

Keunggulan utama: O(n) pada input yang sudah (hampir) terurut. Ini menjadikannya adaptif — ia otomatis memanfaatkan urutan yang sudah ada.

#Selection Sort

Selection Sort memilih elemen terkecil dari unsorted section dan menukarnya dengan elemen pertama di unsorted section.

python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

#Analisis Kompleksitas

Metrik	Nilai
Worst case	O(n²)
Best case	O(n²) — tetap harus scan semua elemen
Rata-rata	O(n²)
Space	O(1) — in-place
Stability	Tidak — menukar elemen bisa mengubah urutan equal

Keunggulan: simpel dan jumlah swap minimum (n-1 swap). Kekurangan: selalu O(n²) bahkan pada input terurut karena harus scan selalu.

Note

Selection Sort cocok untuk situasi di mana write operation mahal (misal EEPROM) karena hanya melakukan n-1 swap, dibandingkan Insertion Sort yang bisa melakukan O(n²) shift.

#Merge Sort

Merge Sort adalah implementasi paradigma divide & conquer untuk sorting: bagi array menjadi dua, sort masing-masing secara rekursif, lalu merge hasilnya.

python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
def merge(left, right):
    result = []
    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])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

#Analisis Kompleksitas

Metrik	Nilai
Worst case	O(n log n)
Best case	Θ(n log n) — selalu membagi
Rata-rata	Θ(n log n)
Space	O(n) — butuh array temporer saat merge
Stability	Ya — `left[i] <= right[j]` mempertahankan urutan

Merge sort adalah model divide & conquer murni — rekursi T(n) = 2T(n/2) + Θ(n) yang menghasilkan Θ(n log n) menurut Master Theorem kasus 2.

#Benchmark: 100, 1000, 10000 Elemen

Untuk melihat perbedaan nyata, jalankan benchmark sederhana:

python

import timeit
import random
 
def benchmark(sort_func, n, trials=10):
    arr = [random.randint(0, n) for _ in range(n)]
    return timeit.timeit(lambda: sort_func(arr.copy()), number=trials) / trials
 
n_values = [100, 1000, 10000]
for n in n_values:
    ins = benchmark(insertion_sort, n)
    sel = benchmark(selection_sort, n)
    mrg = benchmark(merge_sort, n)
    print(f"n={n:>5}: Insertion={ins:.4f}s  Selection={sel:.4f}s  Merge={mrg:.4f}s")

Hasil tipikal menunjukkan:

n=100: ketiganya cepat, Insertion bisa menang karena overhead rekursi Merge.
n=1000: Merge mulai unggul signifikan.
n=10000: Merge ratusan kali lebih cepat dari Insertion/Selection.

Tip

Inilah mengapa asymptotic analysis penting: O(n²) vs O(n log n) terlihat kecil di n kecil, tetapi menjadi perbedaan ratusan kali di n besar. Kalian harus memahami kapan overhead konstanta relevan dan kapan asymptotic dominance yang berlaku.

#Perbandingan Ketiga Algoritma

Kriteria	Insertion	Selection	Merge
Time (worst)	O(n²)	O(n²)	O(n log n)
Time (best)	Θ(n)	O(n²)	Θ(n log n)
Space	O(1)	O(1)	O(n)
Stability	Ya	Tidak	Ya
Adaptif	Ya	Tidak	Tidak
Paradigma	Brute force	Brute force	Divide & conquer

#Penutup

Pada episode 4 ini, kalian telah memahami:

Insertion Sort: adaptif, stabil, O(n²) — bagus untuk data kecil atau hampir terurut.
Selection Sort: simpel, swap minimum, O(n²) — jarang dipakai di praktik.
Merge Sort: O(n log n) stabil, model divide & conquer — standar untuk sorting yang handal.
Benchmark membuktikan perbedaan O(n²) vs O(n log n) di scale besar.

Di episode 5 selanjutnya kita akan membahas Quick Sort, Heap Sort, dan Non-Comparison Sorts — tiga algoritma sorting yang melengkapi gambaran: Quick Sort yang cepat secara average, Heap Sort yang in-place dengan O(n log n), dan Counting/Radix/Bucket Sort yang bisa mencapai O(n) untuk input terbatas. Sampai jumpa di episode 5!