What's the fastest way to alphabetize your bookshelf? - Chand John

Translator: Rahma Kartika Reviewer: Yolanda Raintina

You work at the college library.

Kamu bekerja di perpustakaan kampus.

You're in the middle of a quiet afternoon

Kamu berada di sore yang tenang

when suddenly a shipment of 1,280 different books arrives.

ketika tiba-tiba datang kiriman 1.280 buku yang berbeda.

The books have been dropped of in one long straight line,

Buku-buku itu ditaruh di satu baris lurus,

but they're all out of order,

tapi tidak berurutan,

and the automatic sorting system is broken.

dan sistem penyortir otomatisnya rusak.

To make matters worse, classes start tomorrow,

Lebih buruknya lagi, kelas-kelas dimulai besok,

which means that first thing in the morning,

yang artinya, pagi hari nanti,

students will show up in droves looking for these books.

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

How can you get them all sorted in time?

Bagaimana kamu bisa menyortir semuanya dalam waktu singkat?

One way would be to start at one end of the line with the first pair of books.

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

If the first two books are in order, then leave them as they are.

Jika dua buku pertama sudah urut, biarkan apa adanya.

Otherwise, swap them.

Jika tidak, tukar keduanya.

Then, look at the second and third books,

Kemudian, lihat buku kedua dan ketiga,

repeat the process,

ulangi prosesnya,

and continue until you reach the end of the line.

dan lanjutkan hingga kamu mencapai ujung baris.

At some point, you'll come across the book that should be last,

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

and keep swapping it with every subsequent book,

dan terus tukar dengan buku selanjutnya,

moving it down the line until it reaches the end where it belongs.

pindahkan hingga mencapai ujung di mana seharusnya buku ini berada.

Then, start from the beginning and repeat the process

Kemudian, mulai dari awal dan ulangi prosesnya

to get the second to last book in its proper place,

agar buku kedua hingga terakhir berada di tempat yang tepat,

and keep going until all books are sorted.

dan terus lanjutkan hingga semua buku diurutkan.

This approach is called Bubble Sort.

Pendekatan ini disebut Bubble Sort.

It's simple but slow.

Sederhana tapi lambat.

You'd make 1,279 comparisons in the first round,

Kamu akan membuat 1.279 perbandingan di tahap pertama,

then 1,278, and so on,

kemudian 1.278, dan seterusnya,

adding up to 818,560 comparisons.

sehingga menjadi 818.560 perbandingan.

If each took just one second, the process would take over nine days.

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

A second strategy would be to start by sorting just the first two books.

Cara kedua adalah mulai dengan menyortir dua buku pertama saja.

Then, take the third book and compare it with the book in the second spot.

Kemudian, bandingkan buku ketiga dengan buku kedua.

If it belongs before the second book, swap them,

Jika seharusnya berada di sebelum buku kedua, tukar mereka,

then compare it with the book in the first spot,

kemudian bandingkan dengan buku pertama,

and swap again if needed.

dan tukar lagi jika diperlukan.

Now you've sorted the first three books.

Sekarang, tiga buku pertama sudah urut.

Keep adding one book at a time to the sorted sub-line,

Terus tambah satu buku ke barisan buku yang sudah diurutkan,

comparing and swapping the new book with the one before it

bandingkan, tukar buku yang baru diambil dengan buku sebelumnya

until it's correctly placed among the books sorted so far.

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

This is called Insertion Sort.

Ini disebut Insertion Sort.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

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

On average, we'd expect to only need to compare each book

Biasanya, kita berharap hanya membandingkan setiap buku

to half of the books that came before it.

dengan separuh buku-buku sebelumnya.

In that case, the total number of comparisons

Dalam kasus tersebut, total perbandingan akan menjadi 409.280,

would be 409,280,

taking almost five days.

memerlukan waktu hampir lima hari.

You're still doing way too many comparisons.

Kamu masih melakukan terlalu banyak perbandingan.

Here's a better idea.

Ada cara yang lebih baik.

First, pick a random book.

Pertama, ambil satu buku secara acak.

Call it the partition and compare it to every other book.

Sebut itu sebagai sekat dan bandingkan dengan semua buku lainnya.

Then, divide the line

Kemudian, bagi barisannya menjadi dua

by placing all the books that come before the partition on its left

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

and all the ones that come after it on its right.

dan yang berada di setelahnya di kanannya.

You've just saved loads of time

Kamu sudah menghemat banyak waktu

by not having to compare any of the books on the left

dengan tidak membandingkan semua buku di kiri

to any of the ones on the right ever again.

dengan semua buku di kanan.

Now, looking only at the books on the left,

Sekarang, hanya melihat buku-buku di sebelah kiri,

you can again pick a random partition book

kamu bisa memilih buku sekat secara acak lagi

and separate those books that come before it from those that come after it.

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

You can keep creating sub-partitions like this

Kamu bisa terus membuat sub-sekat seperti ini

until you have a bunch of small sub-lines,

hingga membentuk beberapa sub-baris kecil,

each of which you'd sort quickly using another strategy, like Insertion Sort.

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

Each round of partitioning requires about 1,280 comparisons.

Setiap tahap sekat memerlukan sekitar 1.280 perbandingan.

If your partitions are pretty balanced,

Jika sekatmu cukup seimbang,

dividing the books into 128 sub-lines of ten would take about seven rounds,

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

or 8,960 seconds.

atau 8.960 detik.

Sorting these sub-lines would add about 22 seconds each.

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

All in all, this method known as QuickSort

Metode yang dikenal sebagai QuickSort ini

could sort the books in under three and a half hours.

dapat mengurutkan buku-buku selama kurang dari 3.5 jam.

But there's a catch.

Tapi ada kendalanya.

Your partitions could end up lopsided, saving no time at all.

Kamu tidak bisa menghemat waktu jika sekatmu tidak seimbang.

Luckily, this rarely happens.

Untungnya, ini jarang terjadi.

That's why QuickSort is one of the most efficient strategies

Itulah kenapa QuickSort adalah satu dari strategi yang paling efisien

used by programmers today.

yang digunakan para programmer saat ini.

They use it for things like sorting items in an online store by price,

Mereka menggunakannya untuk menyortir barang di toko online berdasarkan harga,

or creating a list of all the gas stations close to a given location

atau membuat daftar semua SPBU yang dekat lokasi tertentu

sorted by distance.

diurutkan berdasarkan jarak.

In your case, you're done quick sorting with time to spare.

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

Just another high-stakes day in the library.

Hari seperti ini sering terjadi di perpustakaan.