Buka siang dan malamMasuk gratisSilakan sentuh pameran

Ruang F1 · Komputasi

Saksikan enam algoritme pengurutan berlomba.

Jalankan Bubble, Selection, Insertion, Merge, Quick, dan Heap Sort berdampingan. Lihat setiap perbandingan dan pertukaran, dan pahami mengapa ada yang berskala hingga jutaan item sementara yang lain tertinggal.

Cara kerja

Mengurutkan artinya menyusun item berurutan — dari terkecil ke terbesar, A sampai Z. Semua algoritme di bawah memecahkan masalah yang sama; bedanya hanya strategi, dan strategilah yang Anda saksikan. Pilih satu algoritme (atau mode balapan untuk keenamnya sekaligus), pilih input, lalu tekan main. Batang menyala saat mesin bekerja: kuning menandai perbandingan, merah menandai perpindahan atau pertukaran, ungu menandai pivot, dan hijau menandai posisi yang selesai.

Kontrolnya mirip pemutar video karena mesinnya memang begitu: main dan jeda dengan bilah spasi, selangkah demi selangkah dengan panah kanan, ulangi dengan R, daftar baru dengan N, acak denganS, dan kecepatan 0,25× hingga 8×. Panel kode menyorot tiap baris pseudocode saat dieksekusi, sehingga animasi dan program berjalan sinkron. Coba balapan yang sama dua kali: sekali dengan daftar terbalik, sekali hampir terurut, dan saksikan Insertion Sort melompat dari barisan belakang ke depan.

Keenam algoritme

Tiga di antaranya metode kuadratik yang sederhana — mudah ditulis, menyakitkan dalam skala besar. Tiga lainnya metode efisien yang mencapai O(n log n) dengan bagi-dan-taklukkan atau struktur data yang cerdik. Tiap contoh di bawah adalah Python lengkap yang bisa dijalankan, bekerja pada list biasa.

Bubble Sort — pertukaran tetangga

Susuri list sambil membandingkan tetangga dan menukar pasangan yang tak berurutan. Setiap lintasan membuat item terbesar yang belum terurut “mengapung” ke tempat akhirnya, sehingga lintasan berikut bisa satu langkah lebih pendek. Jika satu lintasan penuh tidak menukar apa pun, list sudah terurut dan algoritme berhenti dini — satu-satunya sifat penebusnya, yang memberi O(n) untuk input yang sudah terurut.

def bubble_sort(a):
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a

Selection Sort — pilih yang terkecil, ulangi

Bagi list menjadi depan yang terurut dan sisa yang belum. Tiap langkah, pindai seluruh sisa untuk mencari minimumnya lalu tukar ke tempatnya. Ia selalu melakukan jumlah perbandingan yang sama — sekitar n²/2 — seberapa pun terurutnya input; karena itu kasus terbaik, rata-rata, dan terburuk semuanya O(n²). Kelebihannya adalah melakukan paling banyak n pertukaran, dulu berguna ketika menukar itu mahal.

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

Insertion Sort — cara pemain kartu

Seperti orang mengurutkan kartu di tangan: ambil item berikutnya lalu geser ke kiri melewati semua yang lebih besar hingga pas. Pada data hampir terurut hampir tak ada yang bergerak, sehingga berjalan O(n) — tercepat di ruangan untuk kasus itu, dan alasan pengurutan hibrida nyata memakainya untuk sublist kecil. Pada data terbalik tiap item menempuh jarak penuh: kasus terburuk O(n²). Ia stabil dan tak memakai memori ekstra.

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

Merge Sort — bagi, taklukkan, gabung

Belah list menjadi dua, urutkan tiap belahan dengan cara yang sama (rekursi berhenti pada item tunggal, yang sudah terurut menurut definisi), lalu gabungkan kedua belahan terurut dengan selalu mengambil item depan yang lebih kecil. Belahan selalu seimbang, sehingga tiap tingkat berbiaya O(n) dan ada log n tingkat: O(n log n) terjamin, dalam semua kasus. Harganya O(n) memori ekstra untuk menggabung, dan ia stabil — item yang sama tak pernah saling menyilang.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

Quick Sort — partisi dengan pivot

Pilih pivot, lalu partisi: semua yang lebih kecil ke kiri, semua yang lebih besar ke kanan. Urutkan tiap sisi dengan cara yang sama. Bila pivot jatuh di dekat tengah, rekursi sedalam log n tingkat dan totalnya O(n log n) dengan konstanta mungil dan hanya O(log n) memori ekstra untuk rekursi — umumnya tercepat dalam praktik. Bila jatuh di ujung, satu sisi memuat hampir semuanya dan ia merosot ke O(n²). Simulator ini memilih pivot denganmedian-dari-tiga (item pertama, tengah, dan terakhir), sehingga kasus buruk jarang pada data nyata. Contoh Python di bawah sekadar memakai item terakhir sebagai pivot agar tetap ringkas.

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < p:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        quick_sort(a, lo, i - 1)
        quick_sort(a, i + 1, hi)
    return a

Heap Sort — antrean prioritas yang menyamar

Ubah list menjadi max-heap: pohon biner yang dipadatkan ke dalam array di mana setiap induk lebih besar dari anaknya, sehingga maksimum ada di posisi nol. Ambil maksimum berulang kali, tukar ke ujung, susutkan heap satu, dan pulihkan sifatnya dengan menurunkan puncak baru. O(n log n) terjamin dengan O(1) memori ekstra — tetapi pola akses yang melompat-lompat tak disukai cache prosesor, sehingga biasanya kalah dari Quick dan Merge Sort di stopwatch, meski imbang di atas kertas.

def heap_sort(a):
    def sift(lo, n, i):
        while True:
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < n and a[lo + l] > a[lo + m]:
                m = l
            if r < n and a[lo + r] > a[lo + m]:
                m = r
            if m == i:
                return
            a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
            i = m
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift(0, n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift(0, end, 0)
    return a

Membaca tabel

Big-O menggambarkan pertumbuhan, bukan stopwatch: konstanta dan perangkat keras sengaja diabaikan agarbentuk skalanya terlihat. Tabel di bawah adalah acuan baku (Cormen dkk.,Introduction to Algorithms; Kamus Algoritme dan Struktur Data NIST). “Stabil” berarti item yang sama mempertahankan urutan awal.

AlgoritmeTerbaikRata-rataTerburukMemori ekstraStabil
Bubble SortO(n)O(n²)O(n²)O(1)Ya
Selection SortO(n²)O(n²)O(n²)O(1)Tidak
Insertion SortO(n)O(n²)O(n²)O(1)Ya
Merge SortO(n log n)O(n log n)O(n log n)O(n)Ya
Quick SortO(n log n)O(n log n)O(n²)O(log n)Tidak
Heap SortO(n log n)O(n log n)O(n log n)O(1)Tidak

Coba di simulator: lombakan keenamnya dengan daftar terbalik lalu hampir terurut. Urutan finis berbalik — Insertion Sort melompat dari barisan belakang ke depan — dan tak ada rumus yang mengajarkannya seperti menyaksikannya.

Tiga kekeliruan yang umum

“Quick Sort selalu yang tercepat.” Secara rata-rata Quick Sort termasuk yang tercepat, tetapi Quick Sort sederhana memiliki kasus terburuk O(n²), misalnya ketika pivot selalu jatuh di salah satu ujung daftar. Merge Sort dan Heap Sort tetap O(n log n) apa pun masukannya.

“Metode kuadratik yang sederhana tidak berguna.” Insertion Sort banyak dipakai untuk daftar kecil dan sangat baik pada daftar yang hampir terurut. Rutin pengurutan yang dipakai dalam praktik biasanya hibrida dan beralih ke Insertion Sort untuk potongan kecil.

“Pengurutan stabil adalah pengurutan yang tidak pernah gagal.” Kestabilan punya arti yang tepat: item dengan kunci yang sama mempertahankan urutan yang dimilikinya sebelum diurutkan. Merge Sort dan Insertion Sort stabil; Quick Sort dan Heap Sort, dalam bentuknya yang biasa, tidak.

Pertanyaan pengunjung

Algoritme pengurutan mana yang sebaiknya dipakai di kode nyata?

Hampir selalu pengurutan bawaan bahasa: sorted() Python, Array.sort() JavaScript, atau Arrays.sort() Java untuk objek. Semuanya hibrida rekayasa (Python dan Java memakai Timsort) berwaktu O(n log n), stabil, dan teruji jutaan pengguna. Keenam algoritme di halaman ini mengajarkan ide di balik perkakas itu, bukan menggantikannya.

Jika Bubble Sort lambat, mengapa masih diajarkan?

Karena itu ide pengurutan paling sederhana: bandingkan tetangga, tukar bila tak berurutan, ulangi. Melihatnya kepayahan di samping Merge Sort dalam mode balapan mengajarkan lebih banyak tentang pertumbuhan O(n²) daripada rumus apa pun. Berhenti dini juga menunjukkan algoritme yang sama bisa O(n) untuk input yang sudah terurut dan O(n²) secara umum.

Apa arti pengurutan yang stabil?

Pengurutan stabil mempertahankan item yang sama pada urutan relatif awal. Ini penting saat mengurut dengan lebih dari satu kunci: urutkan kelas berdasarkan nama lalu nilai dengan algoritme stabil, dan murid bernilai sama tetap berurutan alfabet. Merge, Insertion, dan Bubble Sort stabil; Selection, Quick, dan Heap Sort, sebagaimana biasa diimplementasikan, tidak.

Mengapa Quick Sort tidak selalu tercepat meski rata-rata O(n log n)?

Karena kasus terburuknya O(n²): dengan pivot sial, tiap partisi hanya memisahkan satu item. Implementasi bagus menghindarinya dengan pivot median-dari-tiga (seperti di simulator ini) atau pengacakan. Merge Sort menjamin O(n log n) tetapi memakai O(n) memori ekstra; Heap Sort menjamin O(n log n) di tempat, tetapi melompat-lompat di memori, yang tidak disukai cache modern.

Apakah simulator benar-benar menjalankan algoritme, atau hanya animasi?

Benar-benar menjalankannya. Tiap algoritme mengeksekusi logika aslinya dan memancarkan peristiwa langkah — banding, tukar, tulis-ulang, pivot, gabung, heapify — yang diputar ulang oleh grafik animasi. Dalam mode balapan keenamnya memakai input yang sama berdampingan, jadi perbandingannya adil. Mode kata mengurutkan teks tanpa membedakan aksen maupun huruf besar.

Sebenarnya apa yang dihitung notasi Big-O?

Bagaimana jumlah langkah dasar tumbuh mengikuti input, dengan mengabaikan faktor konstan. O(n²) berarti menggandakan input hampir melipatgandakan kerja; O(n log n) berarti menggandakan hanya sedikit lebih dari menggandakan. Pada n = 1.000.000, itulah beda antara sekitar satu triliun operasi dan dua puluh juta — hitungan menit atau bahkan jam versus sepersekian detik.

Sumber dan bacaan lanjutan

Sitasi pameran ini

Eurekarium. (2026). Lab Pengurutan. https://eurekarium.com/id/computing/sorting-lab/

Terakhir diperbarui: