Pengurutan 1: bubble sort, selection sort, dan insertion sort

Selection sort selalu melakukan tepat 45 perbandingan pada daftar berisi 10 nilai apa pun, baik daftarnya mula-mula acak maupun sudah terurut.

Menyusun secara berurutan

Mengurutkan berarti menyusun ulang daftar supaya nilainya berurutan dari yang terkecil ke yang terbesar (atau menurut nama, tanggal, harga, urutan apa pun yang bisa dibandingkan). Ini salah satu pekerjaan yang paling sering dilakukan komputer: kontak di ponsel, hasil pencarian yang diurutkan menurut relevansi, kolom spreadsheet yang diurutkan menurut tanggal. Pengurutan juga mempermudah pekerjaan lain. Seperti yang ditunjukkan unit sebelumnya, daftar terurut bisa dicari dengan pencarian biner, dan nilai kembar dalam daftar terurut letaknya bersebelahan.

Unit ini membahas tiga metode sederhana. Ketiganya bekerja dengan membandingkan dua nilai sekaligus dan memindahkan nilai di dalam daftar yang sama. Kodenya pendek dan mudah diikuti, tetapi ketiganya menjadi sangat lambat pada daftar yang panjang. Memahami mengapa ketiganya melambat adalah persiapan terbaik untuk metode yang lebih cepat di unit berikutnya. Sepanjang unit ini kita menghitung dua hal: perbandingan (bertanya "apakah nilai ini lebih besar daripada nilai itu?") dan pertukaran (menukar dua nilai).

Bubble sort: tukar tetangga yang urutannya salah

Bubble sort menyusuri daftar sambil membandingkan setiap pasangan tetangga. Kalau nilai di kiri lebih besar, keduanya ditukar. Setelah satu lintasan penuh, nilai terbesar sudah terbawa selangkah demi selangkah ke ujung kanan, seperti gelembung yang naik, dan nilai itu tidak perlu dipindahkan lagi. Lintasan berikutnya bisa berhenti satu tempat lebih awal. Perbaikan yang umum adalah memperhatikan lintasan yang sama sekali tanpa pertukaran: artinya semua sudah berurutan, jadi pengurutan bisa berhenti lebih awal.

Ikuti langkahnya pada daftar [5, 1, 4, 2, 8]. Lintasan pertama membandingkan 5 dan 1 (tukar), 5 dan 4 (tukar), 5 dan 2 (tukar), 5 dan 8 (biarkan): daftarnya sekarang [1, 4, 2, 5, 8] dan 8 sudah di tempatnya. Lintasan kedua membandingkan 1 dan 4, 4 dan 2 (tukar), 4 dan 5, sehingga menjadi [1, 2, 4, 5, 8]. Lintasan ketiga membandingkan 1 dan 2, lalu 2 dan 4, tidak menukar apa pun, lalu berhenti. Jumlahnya: 4 + 3 + 2 = 9 perbandingan dan 4 pertukaran.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // tukar
        swapped = true;
      }
    }
    if (!swapped) break;  // sudah terurut
  }
  return a;
}

Selection sort: cari yang terkecil, taruh berikutnya

Selection sort bekerja seperti cara banyak orang mengurutkan kartu di tangan. Telusuri seluruh daftar untuk mencari nilai terkecil, lalu tukar nilai itu ke posisi pertama. Kemudian telusuri sisanya untuk mencari nilai terkecil yang tersisa dan tukar ke posisi kedua, begitu seterusnya. Pada [5, 1, 4, 2, 8] penelusuran pertama menemukan 1 dan menukarnya dengan 5; penelusuran kedua menemukan 2 dan menukarnya dengan 5; dua penelusuran terakhir mendapati 4 dan 5 sudah di tempatnya. Hanya 2 pertukaran, tetapi penelusurannya tetap membandingkan 4 + 3 + 2 + 1 = 10 kali.

Selection sort tidak pernah berhenti lebih awal. Bahkan pada daftar yang sudah terurut, metode ini tetap harus memeriksa setiap nilai yang tersisa untuk memastikan ia mendapat yang terkecil. Untuk n nilai, jumlah perbandingannya selalu (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Untuk 10 nilai hasilnya 45; untuk 100 nilai, 4950; untuk 1000 nilai, 499 500. Kekuatannya adalah jumlah pertukaran yang sedikit: paling banyak n − 1, dan ini penting kalau memindahkan nilai itu mahal.

Insertion sort: sisipkan setiap nilai baru ke tempatnya

Insertion sort menjaga bagian kiri daftar tetap terurut dan memperbesarnya satu nilai setiap kali. Metode ini mengambil nilai berikutnya dan menggesernya ke kiri, bertukar dengan tetangganya, sampai tetangganya tidak lebih besar. Saat itu nilai tersebut sudah berada di tempatnya di antara nilai-nilai yang terurut. Pada daftar yang hampir terurut, setiap nilai baru hanya bergeser satu atau dua langkah, jadi insertion sort sangat cepat di situ. Pada [5, 1, 4, 2, 8] metode ini melakukan 7 perbandingan dan 4 pertukaran.

Menghitung pertukaran: inversi

Ada cara rapi untuk menebak berapa pertukaran yang dibutuhkan bubble sort dan insertion sort. Hitung inversinya: pasangan nilai yang urutannya salah satu sama lain. Dalam [5, 1, 4, 2, 8] inversinya adalah (5, 1), (5, 4), (5, 2), dan (4, 2), semuanya empat. Setiap pertukaran dua tetangga yang urutannya salah memperbaiki tepat satu inversi tanpa membuat inversi baru, jadi kedua metode itu melakukan tepat 4 pertukaran. Daftar terbalik berisi n nilai memiliki semua pasangan terbalik, yaitu n(n − 1)/2 inversi, dan itulah kasus terburuknya.

Setiap sel berisi perbandingan / pertukaran. Daftar contohnya [5, 1, 4, 2, 8]. Bubble sort di sini adalah versi yang berhenti setelah satu lintasan tanpa pertukaran.

Ketiga metode punya kelemahan yang sama. Dalam kasus terburuk, masing-masing membandingkan hampir setiap pasangan nilai, sekitar n²/2 perbandingan. Gandakan panjang daftarnya, maka pekerjaannya naik empat kali. Daftar sepuluh kali lebih panjang berarti pekerjaan seratus kali lebih banyak. Untuk beberapa puluh nilai hal itu hampir tidak terasa; untuk sejuta nilai jelas tidak mungkin, dan unit berikutnya menunjukkan cara yang jauh lebih baik.