The Sorting Algorithm Cup: Round 3
Join us for the third round of the Sorting Algorithm Cup. Today we will see Odd-Even Sort, Pancake Sort, Quick Sort, and Tim Sort.
Welcome back, algorithm aficionados! In this exciting third round of The Sorting Algorithm Cup, we have another four incredible algorithms ready to battle it out for sorting supremacy. Who will emerge victorious and secure a spot in the grand finale? Let’s dive in and see!
In this round, our contenders are Odd-Even Sort, Pancake Sort, Quick Sort, and Tim Sort. Let’s meet our competitors!
Contestant #1: Odd-Even Sort
First up, we have the methodical Odd-Even Sort. This algorithm is a parallel version of Bubble Sort, designed to work efficiently with parallel processing. Odd-Even Sort compares and swaps elements in alternating phases: odd phases compare odd-indexed elements with their next even-indexed neighbours, and even phases compare even-indexed elements with their next odd-indexed neighbours. This back-and-forth comparison helps ensure the list gets sorted efficiently.
- Time Complexity: O(n²)
How it Works:
- In the odd phase, compare all odd-indexed elements with the next even-indexed elements and swap if needed.
- In the even phase, compare all even-indexed elements with the next odd-indexed elements and swap if needed.
- Repeat the above steps until the list is sorted.
Watch it in Action:
Contestant #2: Pancake Sort
Next, bringing a unique twist to sorting, is Pancake Sort! Imagine sorting a stack of pancakes by size, where you can only flip the top portion of the stack. Pancake Sort uses this flipping method to sort the list. It repeatedly finds the largest unsorted element and flips it to the top, then flips it again to its correct position. While not commonly used in practice, Pancake Sort is an interesting algorithm that showcases a different way of thinking about sorting problems.
- Time Complexity: O(n²)
How it Works:
- Find the largest unsorted element.
- Flip the list so that this element is at the top.
- Flip the list again to move this element to its correct position.
- Repeat steps 1–3 until the entire list is sorted.
Watch it in Action:
Contestant #3: Quick Sort
Our third contender is the swift and efficient Quick Sort. This algorithm uses the divide-and-conquer strategy to sort the list. Quick Sort selects a pivot element and partitions the list into two sublists: elements less than the pivot and elements greater than the pivot. It then recursively sorts the sublists. Known for its speed and efficiency, Quick Sort is widely used in practice and is often the go-to algorithm for sorting large datasets.
- Time Complexity: O(n²)
How it Works:
- Choose a pivot element from the list.
- Partition the list into two sublists: elements less than the pivot and elements greater than the pivot.
- Recursively apply the above steps to the sublists.
- Combine the sorted sublists and the pivot to form the final sorted list.
Watch it in Action:
Contestant #4: Tim Sort
Last but definitely not least, we have the hybrid and highly efficient Tim Sort. This algorithm is a combination of Merge Sort and Insertion Sort, designed to perform well on real-world data. Tim Sort divides the list into small runs and sorts them using Insertion Sort. Then, it merges the runs using a merge-like process. Tim Sort is used in Python’s built-in sort function and Java’s Arrays.sort, making it a powerhouse in practical applications.
- Time Complexity: O(n log n)
How it Works:
- Divide the list into small runs.
- Sort each run using Insertion Sort
- Merge the runs using a merge process to produce the final sorted list.
Watch it in Action:
And They’re Off Again!
Running these algorithms on the same 1000 element arrays, here are the results based on 5 iterations per algorithm, where the mean is the average and the range represents the consistency of the algorithm by showing the difference between the highest and lowest times, the smaller it is, the more consistent.
And the one advancing to the grand finale is Quick Sort! As the name suggests, it is the quickest one yet that we have looked at with a mean time of 0.001537 seconds. Will it keep this title or will the next round change everything? Tune in for round 4 to find out!
Stay Tuned
That’s a wrap for today’s race, folks! Make sure to tune in for the next round, where another set of four algorithms will battle it out for a spot in the grand finale.
- Selection Sort
- Shell Sort
- Stooge Sort
- Radix Sort
My favourite, Radix Sort will be in this race so be sure to check out the results. Don’t forget to share your thoughts and predictions in the comments below. Until next time, keep coding and keep sorting!
If you want the code for any of these projects, I have it in my GitHub:
Feel free to ask any questions. Let’s keep this conversation going!
Hi, I’m Batu. I write about Computer Science topics and explain different algorithms to give you potential project ideas. For my stories to pop up on your feed, I’d love for you to follow me (Batu Senturk).
