You work at the college library. You're in the middle of a quiet afternoon when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make matters worse, classes start tomorrow, which means that first thing in the morning, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to start at one end of the line with the first pair of books. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second strategy would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike Bubble Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the partition on its left and all the ones that come after it on its right. You've just saved loads of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most efficient strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given location sorted by distance. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.
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.