Photo by Florian Olivo on Unsplash
As a result of quarantine, people are turning to online alternatives for work, daily tasks, and entertainment. This includes competitive programming, which involves solving problems that require fundamental algorithms and data structures. Within the algorithm subdivision, quick sort is an important algorithm that can be used to solve many problems.
Quick sort is an example of a sorting algorithm and divide and conquer algorithm. With divide and conquer, a problem is repeatedly broken down into smaller problems until those sub-problems become easier to solve. It breaks down the problems recursively so that the original problem is broken down however many times required to make it simpler to solve. This makes quick sort an effective sorting problem, especially when working with a large set of data. Once the quick sort algorithm is used, there will be a sorted array.
The quick sort process begins by choosing a pivot. The element you choose as your pivot can vary; it could be the center, rightmost, or leftmost element. Following the pivot, the next step is partitioning. After completing both of these steps, the pivot should be in its correct place within the array and all the elements to its left should be smaller than it and the elements to the right should be greater than the pivot. The following link shows an example of choosing a pivot and the partitioning process using numbered cups to follow along with: https://www.youtube.com/watch?v=MZaf_9IZCrc.
While this algorithm is fast, the worst time scenario is 0(n2). 0(n2) represents the amount of time the algorithm takes. This occurs when the pivot is the smallest or largest element in the array, which will result in two unbalanced subdivisions. The worst time scenario will take longer when implementing the algorithm as well as create an unbalanced partition. In order to avoid this from happening, make sure to choose a reasonable pivot. On the other hand, the best time scenario is 0(log(n)). 0(log(n)) represents the time the algorithm takes in this scenario. In this situation, the pivot creates two equal divisions within the array and the pivot chosen is the middle element. These two cases, 0(n2) and 0(log(n)), occur due to the pivot chosen in that particular array. For the 0(n2) scenario, the pivot chosen is usually the leftmost or rightmost element and the array is sorted in the same order, reverse order, or the elements are the same. In the best case scenario, the array has an odd number of elements and thus the pivot becomes the middle value. It can also occur in an array with an even number of elements, with each partition having at most n/2 elements, n being the number of elements.
While the quick sort process is a computer algorithm, it can be done with playing cards or any other item to arrange. Practicing this procedure with daily items can help you understand how this algorithm works and applies to computer science. By numbering each item, for example, using the cards ace through seven, and going through the quick sort process, you will be able to see how to choose a pivot and partition. Overall, quick sort is a fundamental algorithm that can be used in competitive coding problems. This algorithm is effective in organizing large sets of data or elements as well as efficient, as it is faster than merge sort, another sorting algorithm. To access examples and problems, check out programming websites like GeeksForGeeks.
Sources:
“Divide and Conquer – Interview Questions & Practice Problems.” Techie Delight, 24 Oct. 2020, www.techiedelight.com/divide-and-conquer-interview-questions/.
https://www.techiedelight.com/quicksort/
“Quicksort Algorithm – C++, Java, and Python Implementation.” Techie Delight, 1 Mar. 2021, www.techiedelight.com/quicksort/.
“When Does the Worst Case of Quicksort Occur?” GeeksforGeeks, 20 Dec. 2016, www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/?ref=rp.
“Analysis of Quicksort (Article) | Quick Sort.” Khan Academy, Khan Academy, www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort.
Websites to practice competitive programming:
https://codeforces.com/
https://www.codechef.com/
https://acm.timus.ru/
https://www.spoj.com/