Hi everyone, inside this article we will see the concept about Quick Sort Analysis.
Quick Sort is a popular and efficient sorting algorithm based on the divide-and-conquer approach. It works by selecting a pivot element from the array, partitioning the array into two sub-arrays based on the pivot, and recursively sorting the sub-arrays.
How Algorithm of Quick Sort works?
Here is how the Quick Sort algorithm works:
- Choose a pivot element from the array. This can be any element in the array, but it is commonly chosen as the last element.
- Partition the array into two sub-arrays, one containing elements smaller than the pivot and the other containing elements greater than or equal to the pivot.
- Recursively apply the Quick Sort algorithm to the two sub-arrays.
- When the sub-arrays have size one or zero, the sorting is complete.
The following is the detailed algorithm for Quick Sort:
- Choose a pivot element from the array. This can be any element in the array, but it is commonly chosen as the last element.
- Partition the array into two sub-arrays, one containing elements smaller than the pivot and the other containing elements greater than or equal to the pivot. This can be done using the following steps:
- Set i to the first element of the array.
- Set j to the last element of the array.
- While i is less than j, do the following:
- Increment i until the element at index i is greater than or equal to the pivot.
- Decrement j until the element at index j is less than the pivot.
- If i is less than j, swap the elements at index i and j.
- Swap the pivot element with the element at index i.
- Recursively apply the Quick Sort algorithm to the sub-arrays to the left and right of the pivot. This can be done using the following steps:
- If the left sub-array has more than one element, apply the Quick Sort algorithm to it.
- If the right sub-array has more than one element, apply the Quick Sort algorithm to it.
- When the sub-arrays have size one or zero, the sorting is complete.
The time complexity of Quick Sort is O(n log n) on average and O(n^2) in the worst case, where n is the size of the input array. The worst-case scenario occurs when the pivot element is the smallest or largest element in the array, which results in an unbalanced partitioning of the array.
To avoid this, various strategies can be used to choose the pivot element, such as selecting a random element or using the median-of-three method. Quick Sort is widely used in practice due to its efficiency and ease of implementation.
Pseudo Code for recursive QuickSort function
function QuickSort(array, start, end)
if start < end then
pivotIndex = Partition(array, start, end)
QuickSort(array, start, pivotIndex - 1)
QuickSort(array, pivotIndex + 1, end)
function Partition(array, start, end)
pivotValue = array[end]
pivotIndex = start
for i = start to end - 1 do
if array[i] <= pivotValue then
Swap(array[i], array[pivotIndex])
pivotIndex = pivotIndex + 1
Swap(array[pivotIndex], array[end])
return pivotIndex
The QuickSort function takes an array, the starting index, and the ending index as input. It recursively partitions the array and sorts the sub-arrays. The Partition function takes an array, the starting index, and the ending index as input.
It partitions the array into two sub-arrays based on the pivot element and returns the index of the pivot element. The Swap function is used to swap two elements in the array.
A Basic Example of Quick Sort with Steps
Suppose we have an array of numbers to be sorted using Quick Sort:
[8, 3, 6, 4, 9, 2, 7, 5]
First, we need to choose a pivot element. For simplicity, let’s choose the last element of the array as the pivot. So, the pivot element is 5.
Next, we partition the array based on the pivot element. We move all the elements smaller than the pivot to the left of the pivot and all the elements greater than the pivot to the right of the pivot. In this example, the array after the first partitioning would be:
[3, 4, 2, 5, 9, 6, 7, 8]
We can see that the pivot element 5 is now in its correct position in the sorted array.
Next, we recursively apply the same partitioning process to the sub-arrays to the left and right of the pivot. We repeat this process until the entire array is sorted.
In this example, we would apply the partitioning process to the left sub-array [3, 4, 2] and the right sub-array [9, 6, 7, 8]. After the partitioning, the left sub-array becomes [2, 3, 4] and the right sub-array becomes [8, 6, 7, 9].
Next, we recursively apply the partitioning process to the left and right sub-arrays again. After partitioning the left sub-array, we get [2, 3], and after partitioning the right sub-array, we get [6, 7, 8, 9].
Finally, the entire array is sorted as [2, 3, 4, 5, 6, 7, 8, 9].
Note that in each partitioning step, we select a pivot element and partition the array into two sub-arrays. The time complexity of Quick Sort depends on how the pivot element is selected and how the partitioning is done. In the worst case, the time complexity is O(n^2), but on average, it is O(n log n).
How to Pick any element as Pivot in Quick sort?
In Quick Sort, the choice of pivot element can affect the performance of the algorithm. There are different strategies for selecting the pivot element:
- Pick the first element as the pivot: This is the simplest strategy, but it can lead to poor performance if the input is already sorted or nearly sorted.
- Pick the last element as the pivot: This is also a simple strategy and can be more effective than picking the first element. However, it can still lead to poor performance in certain cases.
- Pick a random element as the pivot: This strategy can help to avoid worst-case scenarios where the input is already sorted or nearly sorted. By picking a random element, we are less likely to encounter these cases.
- Pick the median of three elements: This strategy involves selecting the pivot as the median of three elements: the first, middle, and last elements of the array. This can help to avoid worst-case scenarios and also tends to be more effective than picking a single element.
- Pick the pivot using a partitioning algorithm: This strategy involves using a separate algorithm to select the pivot element based on the properties of the input array. This can help to ensure that the pivot is a good choice for the input and can lead to better performance. One such algorithm is the “median of medians” algorithm.
Overall, the choice of pivot element in Quick Sort depends on the specific properties of the input array and the desired performance characteristics.
Example Code
/* C++ implementation of QuickSort */
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap two elements
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element and indicates
// the right position of pivot found so far
for (int j = low; j <= high - 1; j++)
{
// If current element is smaller than the 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);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
The above program will output:
Sorted array:
1 5 7 8 9 10Complexity Analysis of Quick Sort
The time complexity of Quick Sort depends on the choice of the pivot element and the partitioning algorithm used. In the average case, Quick Sort has a time complexity of O(n*log n), which makes it one of the fastest sorting algorithms in practice. However, in the worst case, Quick Sort has a time complexity of O(n^2).
The worst-case scenario occurs when the pivot element is either the smallest or largest element in the array, causing the partitioning to result in one subarray of size n-1 and another subarray of size 0. In this case, the recursive calls to Quick Sort do not reduce the size of the problem, leading to a time complexity of O(n^2).
To avoid worst-case scenarios, several strategies can be used to select the pivot element, such as picking a random element or the median of three elements. Additionally, there are several partitioning algorithms that can improve the performance of Quick Sort, such as the “Lomuto partition scheme” and the “Hoare partition scheme“.
In terms of space complexity, Quick Sort has a space complexity of O(log n) due to the recursive calls. This is because Quick Sort uses a divide-and-conquer approach that involves splitting the input array into smaller subarrays. The space required for these subarrays grows logarithmically with the size of the input array.
Where is the Quick sort algorithm used?
Quick Sort is a widely used sorting algorithm that is efficient in practice for sorting large datasets. It is used in many applications where fast sorting is required, such as:
- Database systems: Quick Sort is used for sorting large amounts of data in database systems.
- Computer graphics: Quick Sort is used in computer graphics for sorting pixels and polygons by their properties, such as color or brightness.
- Network routing: Quick Sort is used in network routing algorithms for finding the shortest path between two points.
- Numerical analysis: Quick Sort is used in numerical analysis for solving differential equations and other mathematical problems.
- Programming languages: Quick Sort is used in many programming languages for sorting arrays and lists.
Overall, Quick Sort is a versatile and efficient sorting algorithm that can be used in many different applications.
Advantages of Quick Sort:
- Efficiency: In practice, Quick Sort is one of the fastest sorting algorithms, especially for large datasets. This is because it has a time complexity of O(n*log n) in the average case.
- Space efficiency: Quick Sort has a space complexity of O(log n), which makes it more space-efficient than other sorting algorithms that have a space complexity of O(n).
- Versatility: Quick Sort can be easily implemented in different programming languages and can be used for various data types, such as integers, floats, strings, etc.
Disadvantages of Quick Sort:
- Worst-case scenario: In the worst case, Quick Sort has a time complexity of O(n^2), which occurs when the pivot element is either the smallest or largest element in the array. This can be avoided by selecting a good pivot element.
- Unstable: Quick Sort is an unstable sorting algorithm, which means that it may not preserve the relative order of equal elements in the input array.
- Recursive: Quick Sort is a recursive algorithm, which means that it requires a large amount of function call overhead, which can be a performance issue for very large datasets.
Overall, Quick Sort is a popular and efficient sorting algorithm that has some limitations in terms of worst-case scenarios and stability, but these can be mitigated with good implementation practices.
We hope this article helped you to understand Quick Sort Analysis in a very detailed way.
Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.
If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.