The quick sort algorithm is an efficient sorting algorithm that compares the elements. This sorting algorithm uses a "divide and conquer" method wherein there will be a chosen "pivot" element to be the basis. This pivot element is typically the last element in the array in which the pivot will be the basis for the two sub-arrays that will be created. One sub-array is on the left of the pivot, wherein the elements less than the pivot are stored, while another sub-array is on the right, wherein the elements greater than the pivot are stored.
Referring to the picture below, the counting sort algorithm is applied.
In this example, the original array is [9, -3, 5, 2, 6, 8, -6, 1, 3]. The first step is establishing the pivot element, which is 3 as it is the last element in the array. Element 3 will then be the basis for the creation of the two sub-arrays. The left sub-array is elements less than 3, so it will be [-3, 2, -6, 1]. The right sub-array is elements greater than 3, so it will be [8, 5, 9, 6]. By this time, there will be a total of three sub-arrays of [-3, 2, -6, 1], [3], and [8, 5, 9, 6]. The same steps as the above will be applied to the sub-arrays with more than one element.
For the sake of simplicity, start with the left sub-array. With the array of [-3, 2, -6, 1], the pivot element is element 1. 1 will then be the basis for the left and right sub-arrays to be created. The left sub-array to be created from the pivot element 1 is [-3, 6], while the right is just [2]. Continuing until there is only one element in the left sub-array, -6 is chosen as the pivot element in [-3, -6]. The left sub-array created has only one element of -6, while there is no right sub-array. So, on the left side of the first pivot element 3, the sub-arrays created are [-6], [-3], [1], and [2]. Remove the square brackets to form one sub-array on the left of pivot element 3 and include element 3 itself. Making a sub-array of [-6, -3, 1, 2, 3].
The next step is to focus on the right sub-array of pivot element 3. The sub-array created is [8, 5, 9, 6]. The pivot element to be chosen is 6, which will become the basis for the formation of left and right sub-arrays. On the left sub-array, there is only one element less than 6, which is [5], while on the right sub-array, there are [9, 8]. Since the right sub-array still has two elements, 8 will be chosen as the pivot element. As 9 is greater than the pivot element, it will be placed on the right sub-array. This will make the sub-array on the right side of the first pivot element 3 be [5], [6], [8], and [9].
With the left and right sub-arrays of the first pivot element 3, sorted ascendingly, the forming of the overall sorted array is possible through combining these. The final sorted array is [-6, -3, 1, 2, 3, 5, 6, 8, 9].
The quick sort algorithm is a highly efficient algorithm with an average and best-case time complexity of n logn, where n is the number of elements. However, its worst time complexity is n raised to 2 or n squared, which will happen if an inefficient pivot selection occurs. For the space complexity, the quick sort algorithm has a space complexity of log n.
The use cases and examples for the quick sort algorithm are sorting large datasets efficiently. This can also be used if the average-case performance is to be preferred over the worst-case performance. Lastly, this can be used in sorting algorithm libraries in programming languages.
Overall, the quick sort algorithm offers an efficient way to sort the elements, especially in larger databases. Although its worst-case time complexity is not efficient, its average and best-case complexity is still preferred by programmers.
Posted using Honouree