Merge sort dan quick sort

Divide-and-conquer serta mekanika partisi pada dua pengurutan andalan.

Daftar isi

Merge sort dan quick sort adalah dua pengurutan yang menaungi hampir semua implementasi nyata, dari sorted() Python hingga Arrays.sort Java. Keduanya berdiri di atas satu pola yang sama, yaitu divide-and-conquer, tetapi menaruh kerja kerasnya di tempat yang berbeda. Topik ini membedah mekanika keduanya, mengimplementasikannya dalam Python dan Java dengan penghitung operasi, lalu memperlihatkan kasus terburuk quick sort langsung dari angka keluaran.

Divide-and-conquer sebagai pola bersama#

Strategi divide-and-conquer memecah masukan menjadi dua bagian yang lebih kecil, menyelesaikan tiap bagian secara terpisah, lalu menyatukan hasilnya. Untuk masukan berukuran $n$ , pembagian itu menghasilkan sekitar $\log_2 n$ tingkat pekerjaan, dan setiap tingkat menyapu sebanding dengan $n$ elemen. Hasil kalinya adalah $O(n \log n)$ , kelas yang jauh lebih irit daripada $O(n^2)$ yang dikeluarkan ketiga pengurutan sederhana.

Yang membedakan keduanya adalah letak kerja utamanya. Merge sort memecah tanpa berpikir, tepat dua sama rata, lalu menghabiskan tenaga pada proses penggabungan dua deret terurut. Quick sort sebaliknya, melakukan pekerjaan utama sebelum rekursi dimulai lewat partisi, sehingga tidak ada penggabungan yang perlu dibayar di akhir. Dua gaya ini melahirkan jaminan dan kelemahan yang berbeda, sebagaimana dibedah dua bagian berikutnya.

Merge sort: pecah, gabung, dan jaminan stabilnya#

Merge sort membagi array tepat di tengah hingga setiap potongan tinggal satu elemen, karena satu elemen selalu dapat dianggap terurut. Penggabungan kemudian berjalan dari bawah ke atas, dua deret terurut diamati dari depan sekaligus, elemen yang lebih kecil diambil lebih dahulu, dan sisa deret ditautkan apa adanya. Pada saat nilai kedua deret sama, elemen deret kiri diambil lebih dahulu karena berasal dari posisi yang lebih awal. Ketetapan itulah yang menjadikan merge sort stabil, yaitu mempertahankan urutan asli antarelemen bernilai sama, sifat yang berguna ketika mengurutkan data berlabel.

Penggabungan menyentuh seluruh $n$ elemen di setiap tingkat, dan tingkatnya berjumlah $\log_2 n$ , sehingga jaminan $O(n \log n)$ berlaku untuk kasus terbaik, rata-rata, dan terburuk sekaligus, tanpa bergantung pada keberuntungan masukan. Harga yang dibayar berupa memori tambahan $O(n)$ untuk array bantu, karena penggabungan tidak dapat dilakukan tanpa tempat penampungan hasil. Versi Python di bawah memakai irisan data[:tengah] yang menyalin setiap potongan, sedangkan versi Java berbagi satu array bantu dan bekerja murni pada indeks, bentuk yang lebih hemat alokasi.

Quick sort: partisi in-place dengan skema Lomuto#

Skema Lomuto memilih elemen terakhir sebagai pivot, yaitu elemen acuan partisi. Satu penunjuk menyapu array dari kiri, sedangkan satu batas menandai akhir zona elemen yang tidak lebih besar dari pivot. Setiap kali penunjuk menemukan elemen kecil, batas maju satu langkah dan elemen itu ditukar ke dalam zona, sehingga di akhir sapuan zona kiri berisi semua elemen kecil dan sisanya menunggu di zona kanan.

Penempatan terakhir pivot dituntaskan dengan satu penukaran ke posisi tepat setelah zona kecil, dan posisi itu sudah pasti benar untuk selamanya. Rekursi kemudian menyasar dua sisi yang tersisa tanpa menyertakan pivot, dan tidak ada array tambahan yang dibuat, seluruh proses berjalan in-place. Diagram berikut menangkap satu putaran partisi pada array [7, 3, 9, 1, 5, 8, 2, 6] dengan pivot 6.

Satu putaran partisi Lomuto: elemen yang tidak lebih besar dari pivot berkumpul di kiri, pivot menempati posisi akhirnya

Keluaran partisi pada diagram memperlihatkan zona hijau berisi 3, 1, 5, 2 yang semuanya tidak lebih besar dari 6, sedangkan zona abu berisi 8, 7, 9 yang lebih besar. Isi tiap zona belum tentu terurut, yang dijamin hanya keanggotaannya. Kelemahan skema ini terletak pada pilihan pivot ujung. Pada array yang sudah terurut, pivot selalu menjadi nilai maksimum dan zona kanan selalu kosong, sehingga pembagian menjadi miring ekstrem setiap kali dan kedalaman rekursi mencapai $n$ dengan perbandingan $\frac{n(n-1)}{2}$ , tanda kelas $O(n^2)$ . Solusi yang lazim adalah memilih pivot secara acak atau median dari tiga kandidat.

Implementasi dan penghitungan operasinya#

Kedua algoritma berbagi satu berkas Python. Merge sort ditulis rekursif dengan fungsi penggabung yang menghitung perbandingannya, sedangkan quick sort memakai partisi Lomuto in-place dengan penghitung perbandingan dan penukaran. Driver menjalankan keduanya pada tiga kasus yang sama, ditambah satu demonstrasi kestabilan berupa pasangan nilai dan penanda huruf.

python merge-quick-sort.py

"""Merge sort dan quick sort dengan penghitung perbandingan dan penukaran."""


def merge_sort(data, kunci=lambda elemen: elemen):
    """Urutkan naik secara stabil; kembalikan (hasil, jumlah perbandingan)."""
    if len(data) <= 1:
        return data, 0
    tengah = len(data) // 2
    kiri, p_kiri = merge_sort(data[:tengah], kunci)
    kanan, p_kanan = merge_sort(data[tengah:], kunci)
    hasil, p_gabung = gabung(kiri, kanan, kunci)
    return hasil, p_kiri + p_kanan + p_gabung


def gabung(kiri, kanan, kunci):
    """Gabungkan dua deret terurut menjadi satu deret terurut yang stabil."""
    hasil, perbandingan = [], 0
    i = j = 0
    while i < len(kiri) and j < len(kanan):
        perbandingan += 1
        if kunci(kiri[i]) <= kunci(kanan[j]):   # tanda <= menjaga urutan duplikat
            hasil.append(kiri[i])
            i += 1
        else:
            hasil.append(kanan[j])
            j += 1
    hasil.extend(kiri[i:])
    hasil.extend(kanan[j:])
    return hasil, perbandingan


def quick_sort(data):
    """Urutkan naik secara in-place dengan partisi Lomuto; kembalikan (perbandingan, penukaran)."""
    perbandingan = penukaran = 0

    def partisi(bawah, atas):
        nonlocal perbandingan, penukaran
        pivot = data[atas]
        batas = bawah - 1
        for j in range(bawah, atas):
            perbandingan += 1
            if data[j] <= pivot:
                batas += 1
                if batas != j:
                    data[batas], data[j] = data[j], data[batas]
                    penukaran += 1
        posisi_pivot = batas + 1
        if posisi_pivot != atas:
            data[posisi_pivot], data[atas] = data[atas], data[posisi_pivot]
            penukaran += 1
        return posisi_pivot

    def urutkan(bawah, atas):
        nonlocal perbandingan, penukaran
        if bawah >= atas:
            return
        p = partisi(bawah, atas)
        urutkan(bawah, p - 1)
        urutkan(p + 1, atas)

    urutkan(0, len(data) - 1)
    return perbandingan, penukaran


if __name__ == "__main__":
    dasar = [7, 3, 9, 1, 5, 8, 2, 6]
    kasus = [
        ("sembarang", list(dasar)),
        ("terurut", sorted(dasar)),
        ("terbalik", sorted(dasar, reverse=True)),
    ]
    for nama, asal in kasus:
        print(f"array {nama} {asal}")
        hasil_m, perbandingan_m = merge_sort(asal)
        print(f"  merge sort: perbandingan {perbandingan_m}, hasil {hasil_m}")
        data_q = list(asal)
        perbandingan_q, penukaran_q = quick_sort(data_q)
        print(f"  quick sort: perbandingan {perbandingan_q}, penukaran {penukaran_q}, hasil {data_q}")

    # kestabilan: dua nilai 5 dan dua nilai 2 membawa penanda huruf
    berlabel = [(5, "a"), (2, "b"), (5, "c"), (1, "d"), (2, "e")]
    hasil, _ = merge_sort(berlabel, kunci=lambda pasangan: pasangan[0])
    print("kestabilan :", hasil)

text Keluaran

array sembarang [7, 3, 9, 1, 5, 8, 2, 6]
  merge sort: perbandingan 17, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 14, penukaran 9, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terurut [1, 2, 3, 5, 6, 7, 8, 9]
  merge sort: perbandingan 12, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 28, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terbalik [9, 8, 7, 6, 5, 3, 2, 1]
  merge sort: perbandingan 12, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 28, penukaran 4, hasil [1, 2, 3, 5, 6, 7, 8, 9]
kestabilan : [(1, 'd'), (2, 'b'), (2, 'e'), (5, 'a'), (5, 'c')]

Pada array sembarang, quick sort mencatat 14 perbandingan, lebih sedikit dari 17 milik merge sort, dengan 9 penukaran. Pada array terurut maupun terbalik, perbandingan quick sort melonjak ke 28, tepat $\frac{8 \times 7}{2}$ , tanda partisi yang selalu miring ekstrem, sementara merge sort justru turun ke 12 karena penggabungannya selesai lebih cepat. Baris kestabilan menunjukkan dua pasang duplikat yang penanda hurufnya tetap berurutan sesuai asalnya, b sebelum e dan a sebelum c, bukti konkret bagi klaim stabil.

Versi Java#

Versi Java menaruh kedua penghitung pada dua field statis yang dinolkan sebelum setiap pengukuran, dan memakai satu array bantu yang dibagi ke seluruh rekursi merge sort, sesuai pembahasan memori di atas. Struktur partisinya sama dengan versi Python, termasuk syarat batas != j yang menghindari penukaran elemen ke tempatnya sendiri. Keluaran tujuh baris pertamanya identik dengan versi Python, sedangkan demonstrasi kestabilan dilewatkan karena pasangan berlabel di Java menuntut kelas tambahan tanpa menambah wawasan baru.

java MergeQuickSort.java

import java.util.Arrays;

public class MergeQuickSort {

    static int perbandingan;
    static int penukaran;

    // merge sort: memecah rentang, lalu menggabungkan hasilnya dengan array bantu
    static void mergeSort(int[] data, int[] bantu, int bawah, int atas) {
        if (bawah >= atas) {
            return;
        }
        int tengah = (bawah + atas) / 2;
        mergeSort(data, bantu, bawah, tengah);
        mergeSort(data, bantu, tengah + 1, atas);
        gabung(data, bantu, bawah, tengah, atas);
    }

    // menggabungkan dua bagian terurut; tanda <= menjaga urutan duplikat
    static void gabung(int[] data, int[] bantu, int bawah, int tengah, int atas) {
        for (int i = bawah; i <= atas; i++) {
            bantu[i] = data[i];
        }
        int i = bawah, j = tengah + 1;
        for (int k = bawah; k <= atas; k++) {
            if (i > tengah) {
                data[k] = bantu[j++];
            } else if (j > atas) {
                data[k] = bantu[i++];
            } else {
                perbandingan++;
                if (bantu[i] <= bantu[j]) {
                    data[k] = bantu[i++];
                } else {
                    data[k] = bantu[j++];
                }
            }
        }
    }

    // partisi Lomuto: pivot di ujung kanan, elemen kecil dikumpulkan di kiri
    static int partisi(int[] data, int bawah, int atas) {
        int pivot = data[atas];
        int batas = bawah - 1;
        for (int j = bawah; j < atas; j++) {
            perbandingan++;
            if (data[j] <= pivot) {
                batas++;
                if (batas != j) {
                    int sementara = data[batas];
                    data[batas] = data[j];
                    data[j] = sementara;
                    penukaran++;
                }
            }
        }
        int posisiPivot = batas + 1;
        if (posisiPivot != atas) {
            int sementara = data[posisiPivot];
            data[posisiPivot] = data[atas];
            data[atas] = sementara;
            penukaran++;
        }
        return posisiPivot;
    }

    // quick sort secara in-place pada rentang tertutup
    static void quickSort(int[] data, int bawah, int atas) {
        if (bawah >= atas) {
            return;
        }
        int p = partisi(data, bawah, atas);
        quickSort(data, bawah, p - 1);
        quickSort(data, p + 1, atas);
    }

    public static void main(String[] args) {
        int[][] kasus = {
            {7, 3, 9, 1, 5, 8, 2, 6},
            {1, 2, 3, 5, 6, 7, 8, 9},
            {9, 8, 7, 6, 5, 3, 2, 1},
        };
        String[] namaKasus = {"sembarang", "terurut", "terbalik"};
        for (int k = 0; k < kasus.length; k++) {
            System.out.println("array " + namaKasus[k] + " " + Arrays.toString(kasus[k]));
            int[] bantu = new int[kasus[k].length];
            int[] salinan = kasus[k].clone();
            perbandingan = 0;
            mergeSort(salinan, bantu, 0, salinan.length - 1);
            System.out.println("  merge sort: perbandingan " + perbandingan + ", hasil " + Arrays.toString(salinan));
            salinan = kasus[k].clone();
            perbandingan = 0;
            penukaran = 0;
            quickSort(salinan, 0, salinan.length - 1);
            System.out.println("  quick sort: perbandingan " + perbandingan + ", penukaran " + penukaran + ", hasil " + Arrays.toString(salinan));
        }
    }
}

text Keluaran

array sembarang [7, 3, 9, 1, 5, 8, 2, 6]
  merge sort: perbandingan 17, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 14, penukaran 9, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terurut [1, 2, 3, 5, 6, 7, 8, 9]
  merge sort: perbandingan 12, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 28, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terbalik [9, 8, 7, 6, 5, 3, 2, 1]
  merge sort: perbandingan 12, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 28, penukaran 4, hasil [1, 2, 3, 5, 6, 7, 8, 9]

bash

# menjalankan berkas Java tunggal tanpa tahap kompilasi terpisah
java MergeQuickSort.java

text Keluaran

array sembarang [7, 3, 9, 1, 5, 8, 2, 6]
  merge sort: perbandingan 17, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 14, penukaran 9, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terurut [1, 2, 3, 5, 6, 7, 8, 9]
  merge sort: perbandingan 12, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 28, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terbalik [9, 8, 7, 6, 5, 3, 2, 1]
  merge sort: perbandingan 12, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  quick sort: perbandingan 28, penukaran 4, hasil [1, 2, 3, 5, 6, 7, 8, 9]

Kesalahan umum#

Memakai < pada penggabungan merge sort. Ketika dua nilai sama, elemen deret kanan terambil lebih dahulu dan urutan asli duplikat terbalik tanpa terlihat. Tanda <= adalah syarat kestabilan, bukan sekadar kebiasaan penulisan.
Rekursi quick sort menyertakan posisi pivot. Memanggil rekursi pada rentang yang masih memuat pivot membuat pivot dipecah ulang dan perulangan tidak pernah berhenti. Kedua panggilan rekursi harus menghormati rentang bawah sampai p - 1 dan p + 1 sampai atas.
Menganggap merge sort bekerja tanpa memori tambahan. Array bantu berukuran $O(n)$ adalah bagian dari algoritmanya, bukan pilihan implementasi. Pada lingkungan dengan memori sempit, quick sort atau heap sort menjadi kandidat yang lebih cocok.

Ringkasan#

Divide-and-conquer menghasilkan $\log_2 n$ tingkat dengan pekerjaan $n$ per tingkat, sehingga keduanya berada di kelas $O(n \log n)$ pada kasus normal.
Merge sort stabil, berlaku $O(n \log n)$ di semua kasus, dan membayar memori tambahan $O(n)$ untuk penggabungannya.
Quick sort bekerja in-place lewat partisi Lomuto, tetapi pivot ujung pada data terurut memicu kasus terburuk $O(n^2)$ .
Data keluaran memperlihatkan keduanya, 14 melawan 17 perbandingan pada array sembarang, lalu 28 melawan 12 ketika quick sort jatuh ke kasus terburuknya.

Referensi#

Merge sort — Wikipedia — mekanika pembagian dan penggabungan serta sifat stabil pada merge sort.
Quicksort — Wikipedia — skema partisi, pilihan pivot, dan analisis kasus terburuk quick sort.