Pengurutan 2: merge sort dan quicksort

Mengurutkan sejuta nilai dengan membandingkan setiap pasangan butuh sekitar 500 miliar perbandingan; merge sort hanya butuh sekitar 20 juta.

Pecah masalahnya, selesaikan tiap separuh

Metode di unit sebelumnya bekerja pada seluruh daftar sekaligus dan harus membayarnya dengan sekitar n² perbandingan. Dua metode di unit ini memakai rencana lain yang disebut divide and conquer (bagi dan taklukkan). Pecah daftar menjadi bagian-bagian yang lebih kecil, urutkan setiap bagian dengan metode yang sama, lalu gabungkan bagian-bagian yang sudah terurut. Pemecahan berlanjut sampai sebuah bagian hanya berisi satu nilai atau kosong, dan daftar berisi satu nilai pasti sudah terurut. Karena metode ini memanggil dirinya sendiri pada daftar yang lebih kecil, metode ini bersifat rekursif (unit 6 membahas rekursi lebih rinci).

Merge sort: kerjanya ada pada penggabungan

Merge sort memotong daftar menjadi dua, mengurutkan separuh kiri, mengurutkan separuh kanan, lalu menggabungkan kedua separuh yang terurut menjadi satu. Bagian cerdiknya ada pada penggabungan. Dua daftar terurut bisa digabungkan hanya dengan melihat nilai terdepannya. Bandingkan kedua nilai terdepan, tuliskan yang lebih kecil, lalu lewati nilai itu. Ulangi sampai salah satu daftar kosong, lalu salin sisa daftar yang lain. Penggabungan [1, 4, 7] dan [2, 3, 8] berjalan 1 (1 lawan 2), 2 (4 lawan 2), 3 (4 lawan 3), 4 (4 lawan 8), 7 (7 lawan 8), lalu 8 disalin: 5 perbandingan untuk 6 nilai. Penggabungan dua daftar yang seluruhnya berisi n nilai tidak pernah butuh lebih dari n − 1 perbandingan.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // sudah terurut
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Mengapa ini cepat? Bayangkan pembagian dua itu sebagai tingkat-tingkat. Daftar berisi 8 nilai terpecah menjadi 2 daftar berisi 4, lalu 4 daftar berisi 2, lalu 8 daftar berisi 1: tiga tingkat, karena 8 bisa dibagi dua sebanyak 3 kali. Di setiap tingkat, semua penggabungan bersama-sama menyentuh setiap nilai satu kali, jadi satu tingkat paling banyak memakan sekitar n perbandingan. Dengan log₂ n tingkat, jumlahnya sekitar n log₂ n. Untuk sejuta nilai, itu sekitar 20 juta perbandingan, dibandingkan sekitar 500 miliar untuk metode yang membandingkan pasangan demi pasangan. Jika dipecah menjadi [38, 27, 43, 3] dan [9, 82, 10], seperti di laboratorium, daftar [38, 27, 43, 3, 9, 82, 10] butuh 14 perbandingan; kode di atas memecahnya menjadi 3 dan 4 dan butuh 13.

Harganya adalah memori. Penggabungan butuh tempat untuk menulis hasilnya, jadi merge sort memakai daftar kedua yang sama besar dengan masukannya. Merge sort juga stabil: nilai-nilai yang sama besar tetap dalam urutan aslinya, karena penggabungan mengambil dari daftar kiri saat kedua nilai terdepan sama. Hal ini penting saat kamu mengurutkan tabel menurut satu kolom lalu kolom lain, misalnya menurut kota lalu menurut nama.

Quicksort: pecah di sekitar pivot

Quicksort memecah daftar dengan cara yang berbeda. Metode ini memilih satu nilai, yaitu pivot, lalu menyusun ulang daftar sehingga semua yang lebih kecil daripada pivot berada di depannya dan sisanya di belakangnya. Langkah ini disebut partisi. Sekarang pivot sudah berada di tempat akhirnya, dan kedua sisi bisa diurutkan terpisah dengan metode yang sama. Tidak ada yang perlu digabungkan sesudahnya, karena setiap nilai di kiri sudah lebih kecil daripada setiap nilai di kanan.

Laboratorium ini memakai versi buku pelajaran yang umum, yang mengambil nilai terakhir setiap bagian sebagai pivot. Pada [5, 1, 4, 2, 8] pivot 8 dibandingkan dengan empat nilai lain yang semuanya lebih kecil, jadi 8 tetap di ujung. Bagian berikutnya, [5, 1, 4, 2], memakai pivot 2: hanya 1 yang lebih kecil, jadi setelah dua pertukaran daftarnya menjadi [1, 2, 4, 5, 8]. Satu perbandingan lagi menyelesaikan [4, 5]. Jumlahnya: 8 perbandingan dan 2 pertukaran.

Kalau pivot jatuh di dekat tengah, setiap pemecahan membagi dua masalahnya dan quicksort butuh sekitar n log₂ n perbandingan, seperti merge sort. Metode ini juga bekerja di dalam daftar asli tanpa salinan kedua. Namun pivot yang buruk merugikan. Kalau daftarnya sudah terurut dan pivot selalu nilai terakhir, setiap pemecahan hanya melepas satu nilai, dan quicksort kembali ke sekitar n²/2 perbandingan: 10 untuk [1, 2, 3, 4, 5], sama dengan selection sort. Pustaka sungguhan menghindarinya dengan memilih pivot lebih hati-hati, misalnya secara acak atau sebagai nilai tengah dari tiga nilai sampel.