Apa cara tercepat untuk mengurutkan buku sesuai abjad? - Chand John

Simak materi selengkapnya: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Kamu bekerja di perpustakaan kampus. Kamu berada di suatu sore yang tenang ketika tiba-tiba datang kiriman 1.280 buku. Buku-buku itu ditaruh di satu baris lurus, tapi tidak berurutan, dan mesin penyortir otomatis rusak. Bagaimana kamu menyortir buku-buku itu dalam waktu singkat? Chand John menunjukkan caranya, menjelaskan bagaimana algoritma membantu pustakawan dan mesin pencari menyortir informasi dengan cepat.

Materi oleh Chand John, animasi oleh Anton Trofimov.

Kamu bekerja di perpustakaan kampus.

Kamu berada di sore yang tenang

ketika tiba-tiba datang kiriman
1.280 buku yang berbeda.

Buku-buku itu ditaruh di satu baris lurus,

tapi tidak berurutan,

dan sistem penyortir otomatisnya rusak.

Lebih buruknya lagi,
kelas-kelas dimulai besok,

yang artinya,
pagi hari nanti,

para siswa akan berbondong-bondong
mencari buku-buku ini.

Bagaimana kamu bisa menyortir semuanya
dalam waktu singkat?

Salah satu caranya adalah memulai dari
sepasang buku di ujung barisan.

Jika dua buku pertama sudah urut,
biarkan apa adanya.

Jika tidak, tukar keduanya.

Kemudian, lihat buku kedua dan ketiga,

ulangi prosesnya,

dan lanjutkan hingga kamu mencapai
ujung baris.

Kadang, kamu akan menemukan buku
yang seharusnya diletakkan di akhir,

dan terus tukar dengan buku selanjutnya,

pindahkan hingga mencapai ujung
di mana seharusnya buku ini berada.

Kemudian, mulai dari awal
dan ulangi prosesnya

agar buku kedua hingga terakhir
berada di tempat yang tepat,

dan terus lanjutkan hingga semua buku
diurutkan.

Pendekatan ini disebut Bubble Sort.

Sederhana tapi lambat.

Kamu akan membuat 1.279 perbandingan
di tahap pertama,

kemudian 1.278, dan seterusnya,

sehingga menjadi 818.560 perbandingan.

Jika tiap proses perlu waktu satu detik,
maka akan memakan waktu lebih dari 9 hari.

Cara kedua adalah mulai dengan
menyortir dua buku pertama saja.

Kemudian, bandingkan buku ketiga
dengan buku kedua.

Jika seharusnya berada
di sebelum buku kedua, tukar mereka,

kemudian bandingkan dengan buku pertama,

dan tukar lagi jika diperlukan.

Sekarang, tiga buku pertama sudah urut.

Terus tambah satu buku
ke barisan buku yang sudah diurutkan,

bandingkan, tukar buku yang baru diambil
dengan buku sebelumnya

hingga berada di tempat yang tepat
di antara buku-buku yang telah disortir.

Ini disebut Insertion Sort.

Tidak seperti Bubble Sort, ini tidak perlu
membandingkan tiap pasang buku.

Biasanya, kita berharap hanya
membandingkan setiap buku

dengan separuh buku-buku sebelumnya.

Dalam kasus tersebut, total perbandingan
akan menjadi 409.280,

memerlukan waktu hampir lima hari.

Kamu masih melakukan
terlalu banyak perbandingan.

Ada cara yang lebih baik.

Pertama, ambil satu buku secara acak.

Sebut itu sebagai sekat
dan bandingkan dengan semua buku lainnya.

Kemudian, bagi barisannya menjadi dua

dengan menaruh semua buku yang ada
di depan sekat di sebelah kiri

dan yang berada di setelahnya di kanannya.

Kamu sudah menghemat banyak waktu

dengan tidak membandingkan
semua buku di kiri

dengan semua buku di kanan.

Sekarang, hanya melihat buku-buku
di sebelah kiri,

kamu bisa memilih buku sekat
secara acak lagi

dan memisahkan buku yang ada di sebelumnya
dengan yang ada di setelahnya.

Kamu bisa terus membuat sub-sekat
seperti ini

hingga membentuk beberapa sub-baris kecil,

masing-masing kamu urutkan dengan
strategi lain, seperti Insertion Sort.

Setiap tahap sekat memerlukan
sekitar 1.280 perbandingan.

Jika sekatmu cukup seimbang,

buku-buku dapat dibagi menjadi 128 baris
dengan 10 buku dalam 7 tahap

atau 8.960 detik.

Mengurutkan sub-baris ini akan menambah
masing-masing sekitar 22 detik.

Metode yang dikenal sebagai QuickSort ini

dapat mengurutkan buku-buku
selama kurang dari 3.5 jam.

Tapi ada kendalanya.

Kamu tidak bisa menghemat waktu
jika sekatmu tidak seimbang.

Untungnya, ini jarang terjadi.

Itulah kenapa QuickSort adalah
satu dari strategi yang paling efisien

yang digunakan para programmer saat ini.

Mereka menggunakannya untuk menyortir
barang di toko online berdasarkan harga,

atau membuat daftar semua SPBU
yang dekat lokasi tertentu

diurutkan berdasarkan jarak.

Dalam kasusmu, kamu selesai mengurutkan
dengan waktu yang masih tersisa.

Hari seperti ini sering terjadi
di perpustakaan.