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.
Bạn làm việc tại thư viện trường đại học. Trong một buổi chiều bình lặng, bỗng có một đơn hàng với 1 280 cuốn sách khác nhau được chuyển đến. Các cuốn sách được xếp thành một hàng dài nhưng chẳng theo thứ tự nào hết và hệ thống sắp xếp tự động thì lại hỏng mất rồi. Còn tệ hơn nữa là các lớp sẽ bắt đầu học vào ngày mai nghĩa là ngay từ sáng sớm, sinh viên sẽ ào đến tìm sách. Làm cách nào để bạn sắp xếp chúng cho kịp thời gian đây? Cách đầu tiên là bạn bắt đầu một vài cuốn ở một đầu của dãy sách. Nếu hai cuốn đầu tiên theo thứ tự, hãy để nguyên chúng ở đó. Nếu không thì hãy xếp lại. Tiếp theo, tìm cuốn sách thứ hai và thứ ba lặp lại quá trình trên và tiếp tục cho đến cuối hàng. Ở một thời điểm nào đó, bạn sẽ bắt gặp cuốn sách ở thứ tự cuối hãy tráo nó với mọi cuốn sách tiếp sau tiếp tục như vậy cho tới khi nó về đúng chỗ ở cuối hàng. Tiếp theo, bắt đầu từ đầu và lặp lại để đưa cuốn sách thứ hai từ dưới lên về đúng chỗ và cứ thế cho tới khi tất cả chỗ sách được sắp xếp hết. Phương pháp này gọi là Sắp xếp Nổi bọt Tuy đơn giản nhưng lại chậm chạp. Bạn phải so sánh 1 279 lần trong lượt sắp xếp đầu tiên rồi đến 1 278 lần và tiếp tục như thế tổng cộng lại sẽ là 818 560 lượt so sánh. Nếu mỗi lượt kéo dài 1 giây, cả quá trình sẽ cần tới hơn 9 ngày để hoàn thành. Phương án thứ hai là bắt đầu sắp xếp với hai cuốn sách đầu tiên thôi. Rồi lấy cuốn thứ ba và so với cuốn ở vị trí thứ hai. Nếu nó đứng trước cuốn ở vị trí thứ hai, hãy tráo chúng rồi so với cuốn ở vị trí đầu và tráo lần nữa nếu cần thiết. Giờ bạn đã tráo xong ba cuốn sách đầu tiên. Cứ tiếp tục thêm từng cuốn sách một vào dãy sách đã sắp xếp so sánh và tráo cuốn mới với cuốn trước nó cho tới khi chúng được đặt đúng vị trí trong đống sách đã sắp xếp. Cách này được gọi là Sắp xếp Chèn. Khác với Sắp xếp Nổi bọt, cách này không bắt buộc bạn phải so sánh từng cặp. Trung bình, chúng ta chỉ cần phải so sánh mỗi cuốn sách với một nửa số sách trước nó. Trong trường hợp đó, số lượt so sánh sẽ là 409 280 mất tới gần 5 ngày. Bạn vẫn phải so sánh quá nhiều lần. Ở đây có một cách hay hơn nè. Đầu tiên, hãy chọn ngẫu nhiên một cuốn sách Hãy coi nó là Vách Ngăn và so sánh nó với tất cả các cuốn sách khác. Sau đó, chia dãy sách ra bằng cách đặt tất cả những cuốn có thứ tự trước Vách Ngăn ở bên tay trái và những cuốn sau Vách Ngăn ở bên tay phải Bạn vừa tiết kiệm được thời gian vì không phải so sánh bất kì cuốn sách nào ở bên trái với các cuốn sách ở bên phải. Giờ, hãy chỉ tập trung vào số sách bên tay trái bạn lại có thể lựa chọn một Vách Ngăn bất kì và chia số sách đó thành những cuốn đứng trước và đứng sau Bạn có thể tiếp tục tạo ra các Vách Ngăn phụ như vậy cho tới khi có rất nhiều dãy sách phụ với mỗi dãy, bạn có thể sắp xếp nhanh chóng bằng phương pháp Sắp xếp Chèn Mỗi lần chia ngăn cần khoảng 1 280 lượt so sánh Nếu các Vách Ngăn của bạn khá đồng đều chia số sách thành 128 dãy phụ gồm 10 cuốn sẽ mất khoảng 7 lượt hay 8 960 giây. Phân loại hết các dãy phụ này sẽ tốn thêm khoảng 22 giây mỗi lần. Nói chung, phương pháp có tên Sắp xếp Nhanh này có thể giúp bạn phân loại sách trong vòng chưa đầy 3 tiếng rưỡi Tuy nhiên, vẫn có bẫy. Các Vách Ngăn của bạn có thể bị lệch và sẽ chẳng tiết kiệm được thời gian May mắn là điều này rất hiếm khi xảy ra Vì vậy nên Sắp xếp Nhanh là một trong những phương án hữu hiệu nhất được các nhà lập trình sử dụng ngày nay. Họ dùng nó để sắp xếp hàng theo giá cả trên cửa hàng trực tuyến hoặc tạo ra danh sách các cây xăng gần với một địa điểm nhất định theo khoảng cách. Trong trường hợp của bạn, bạn có thể sắp xếp nhanh mà vẫn còn thừa thời gian Và đó lại là một ngày bận rộn khác trong thư viện