Imagine you work at a college library, and you’re having a quiet day. Suddenly, a delivery of 1,280 books arrives. They’re all in one big line but entirely out of order.
To make things worse, the automatic sorting system is broken. And students are coming tomorrow looking for these books!
What can you do to get these books sorted in time? Here are three ways to sort them, and we promise to keep it fun and easy to understand.
Table of Contents
Bubble Sort: Simple but Slow
You start at one end of the line and compare pairs of books. If they’re in order, leave them as they are, but if not, swap them around.
Then move on to the next pair and keep going until you reach the end of the line. This may sound simple enough, but it can take a long time because you must keep going back and forth until everything is sorted.
In fact, if you had to sort 1,280 books using Bubble Sort and each comparison took just one second, it would take over nine days! That’s longer than most of us would be willing to wait for a book to arrive in the mail.
Insertion Sort: Still Slow but Better
A second strategy would be sorting just the first two books. Then, compare the third book with the book in the second spot. If it belongs before the second book, swap them, compare it with the book in the first spot, and change 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.
With Insertion Sort, you usually won’t have to compare every pair of books. You’d only need to compare each book to half of the books that came before it. That means you’d only have to make about 409,280 comparisons, which would take almost five days. It’s still a lot of work but faster than Bubble Sort.
QuickSort: Efficient and Fast
Here’s a better idea. First, pick a random book and call it the partition. Then, compare it to every other book and divide the line into two parts: books that come before the partition on the left and those that come after it on the right.
Now, you only need to compare the books on the left with each other and the books on the right with each other. Repeat the process with the left side, creating smaller sub-lines until you have many small sub-lines, which you can quickly sort using a more straightforward method like Insertion Sort.
QuickSort is fast and efficient, but there’s a catch: your partitions could end up lopsided, and you won’t save time.
When it comes to sorting a bunch of books it can be daunting. However, there’s a solution that programmers use to sort things quickly and efficiently. It’s called QuickSort, and it’s one of the best ways to get the job done.
Once you get the hang of it, you can use this technique for all sorts of things, from online shopping to find the nearest gas station. Plus, it’s so fast that you’ll have plenty of time to kick back and relax while your books are sorted in no time.
To access relevant information, check out the following blogs:
- Kangaroo Math Blog for Mathematics
- Kancil Science Blog for Science
- Beaver Computational Thinking Blog for Computer Science
- Kijang Economy Blog for Economics.
