The algorithm was developed by a British computer scientist Tony Hoare in 1959. The name "Quick Sort" comes from the fact that, quick sort is capable of sorting a list of data elements significantly faster (twice or thrice faster) than any of the common sorting algorithms. It is one of the most efficient sorting algorithms and is based on the splitting of an array (partition) into smaller ones and swapping (exchange) based on the comparison with 'pivot' element selected. Due to this, quick sort is also called as "Partition Exchange" sort. Like Merge sort, Quick sort also falls into the category of divide and conquer approach of problem-solving methodology.
Application
Quicksort works in the following way
Before diving into any algorithm, its very much necessary for us to understand what are the real world applications of it. Quick sort provides a fast and methodical approach to sort any lists of things. Following are some of the applications where quick sort is used.
Commercial computing: Used in various government and private organizations for the purpose of sorting various data like sorting of accounts/profiles by name or any given ID, sorting transactions by time or locations, sorting files by name or date of creation etc.
Numerical computations: Most of the efficiently developed algorithms use priority queues and in turn sorting to achieve accuracy in all the calculations.
Information search: Sorting algorithms aid in better search of information and what faster way exists than to achieve sorting using quick sort.
Basically, quick sort is used everywhere for faster results and in the cases where there are space constraints.
Explanation
Taking the analogical view in perspective, consider a situation where one had to sort the papers bearing the names of the students, by name from A-Z. One might use the approach as follows:
Select any splitting value, say L. The splitting value is also known as Pivot.
Divide the stack of papers into two. A-L and M-Z. It is not necessary that the piles should be equal.
Repeat the above two steps with the A-L pile, splitting it into its significant two halves. And M-Z pile, split into its halves. The process is repeated until the piles are small enough to be sorted easily.
Ultimately, the smaller piles can be placed one on top of the other to produce a fully sorted and ordered set of papers.
The approach used here is reduction at each split to get to the single-element array.
At every split, the pile was divided and then the same approach was used for the smaller piles by using the method of recursion.
Technically, quick sort follows the below steps: Step 1 − Make any element as pivot Step 2 − Partition the array on the basis of pivot Step 3 − Apply quick sort on left partition recursively Step 4 − Apply quick sort on right partition recursively
Quick Sort Example:
Problem Statement
Consider the following array: 50, 23, 9, 18, 61, 32. We need to sort this array in the most efficient manner without using extra place (in place sorting).
Solution
Step 1:
Make any element as pivot: Decide any value to be the pivot from the list. For convenience of code, we often select the rightmost index as pivot or select any at random and swap with rightmost. Suppose for two values “Low” and “High” corresponding to the first index and last index respectively.
1. In our case low is 0 and high is 5.
2. Values at low and high are 50 and 32 and value at pivot is 32.
Partition the array on the basis of pivot: Call for partitioning which rearranges the array in such a way that pivot (32) comes to its actual position (of the sorted array). And to the left of the pivot, the array has all the elements less than it, and to the right greater than it.
1. In the partition function, we start from the first element and compare it with the pivot. Since
50 is greater than 32, we don’t make any change and move on to the next element 23.
2. Compare again with the pivot. Since 23 is less than 32, we swap 50 and 23. The array
becomes 23, 50, 9, 18, 61, 32
3. We move on to the next element 9 which is again less than pivot (32) thus swapping it with 50
makes our array as 23, 9, 50, 18, 61, 32.
4. Similarly, for next element 18 which is less than 32, the array becomes 23, 9, 18, 50, 61, 32.
Now 61 is greater than pivot (32), hence no changes.
5. Lastly, we swap our pivot with 50 so that it comes to the correct position.
Thus the pivot (32) comes at its actual position and all elements to its left are lesser, and all elements to the right are greater than itself.
Step 2: The main array after the first step becomes
23, 9, 18, 32, 61, 50Step 3: Now the list is divided into two parts:
Sublist before pivot element
Sublist after pivot element
Step 4: Repeat the steps for the left and right sublists recursively. The final array thus becomes 9, 18, 23, 32, 50, 61.
The following diagram depicts the workflow of the Quick Sort algorithm which was described above.
Pseudocode of Quick Sort Algorithm:
Quick Sort
/**
* The main function that implements quick sort.
* @Parameters: array, starting index and ending index
*/
quickSort(arr[], low, high)
{
if (low < high)
{
// pivot_index is partitioning index, arr[pivot_index] is now at correct place in sorted array
pivot_index = partition(arr, low, high);
quickSort(arr, low, pivot_index - 1); // Before pivot_index
quickSort(arr, pivot_index + 1, high); // After pivot_index
}
}
Partition Method
/**
* The function selects the last element as pivot element, places that pivot element correctly in the array in such a way
* that all the elements to the left of the pivot are lesser than the pivot and
* all the elements to the right of pivot are greater than it.
* @Parameters: array, starting index and ending index
* @Returns: index of pivot element after placing it correctly in sorted array
*/
partition (arr[], low, high)
{
// pivot - Element at right most position
pivot = arr[high];
i = (low - 1); // Index of smaller element
for (j = low; j <= high-1; j++)
{
// If current element is smaller than the pivot, swap the element with pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
Implementation of Quick Sort
Following are C, C++, Java and Python implementations of Quicksort.
Complexity Analysis
Time Complexity of Quick sort
Best case scenario: The best case scenario occurs when the partitions are as evenly balanced as possible, i.e their sizes on either side of the pivot element are either are equal or are have size difference of 1 of each other.
Case 1: The case when sizes of sublist on either side of pivot becomes equal occurs when the subarray has an odd number of elements and the pivot is right in the middle after partitioning. Each partition will have (n-1)/2 elements.
Case 2: The size difference of 1 between the two sublists on either side of pivot happens if the subarray has an even number, n, of elements. One partition will have n/2 elements with the other having (n/2)-1.
In either of these cases, each partition will have at most n/2 elements, and the tree representation of the subproblem sizes will be as below:
The best case complexity of quick sort algorithm is O(log n)
Worst case scenario: This happens when we encounter the most unbalanced partitions possible, then the original call takes n time, the recursive call on n-1 elements will take (n-1) time, the recursive call on (n-2) elements will take (n-2) time, and so on. The worst case time complexity of Quick Sort would be O(n2).
Space Complexity of Quick sort
The space complexity is calculated based on the space used in the recursion stack. The worst case space used will be O(n) . The average case space used will be of the order O(log n). The worst case space complexity becomes O(n), when the algorithm encounters its worst case where for getting a sorted list, we need to make n recursive calls.
Resource: Interviewbit.com
The Tech Platform
Comments