Principles of Quick Sort
Quick Sort is a comparison-based sorting algorithm that follows the divide and conquer strategy. It works by selecting a pivot element from the array, partitioning the array into two subarrays based on the pivot, and recursively sorting each subarray.
Algorithm
- Choose a Pivot: Select a pivot element from the array. This pivot element can be chosen in various ways, such as selecting the first, last, or middle element of the array.
- Partitioning: Rearrange the elements of the array so that all elements less than the pivot are moved to its left, and all elements greater than the pivot are moved to its right. The pivot itself is placed in its correct position in the sorted array.
- Recursively Sort Subarrays: Recursively apply the Quick Sort algorithm to the subarrays on the left and right of the pivot until the entire array is sorted.
Dry Run:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 19 | 7 | 15 | 12 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8Choose the Pivot Point:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 19 | 7 | 15 | 12 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^
|
pivotFind Perfect Position for the Pivot Point:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 19 | 7 | 15 | 12 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^
| |
Low High
|
pivot
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 19 | 7 | 15 | 12 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^
| | |
i Low High
| |
j pivot
Iterate while j < high
j = 0
if(arr[j] < pivot)
19 < 13
False
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 19 | 7 | 15 | 12 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
-1 0 1 2 3 4 5 6 7 8
^ ^ ^ ^
| | | |
i Low | High
| |
j pivot
j = 1
if(arr[j] < pivot)
7 < 13
True
i++ = -1++ = 0
swap(arr[i], arr[j])
swap(arr[0], arr[1])
19 <-> 7
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 19 | 15 | 12 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^
| | |
Low | High
| j |
i pivot
j = 2
if(arr[j] < arr[pivot])
15 < 13
False
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 19 | 15 | 12 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^
| | |
Low | High
| j |
i pivot
j = 3
if(arr[j] < arr[pivot])
12 < 13
True
i++ = 0++ = 1
swap(arr[i], arr[j])
swap(arr[1], arr[3])
19 <-> 12
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 12 | 15 | 19 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^ ^
| | | |
Low | | High
| | |
i j pivot
j = 4
if(arr[j] < arr[pivot])
16 < 13
False
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 12 | 15 | 19 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^ ^
| | | |
Low | | High
| | |
i j pivot
j = 5
if(arr[j] < arr[pivot])
18 < 13
False
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 12 | 15 | 19 | 16 | 18 | 4 | 11 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^ ^
| | | |
Low | | High
| | |
i j pivot
j = 6
if(arr[j] < arr[pivot])
4 < 13
True
i++ = 1++ = 2
swap(arr[i], arr[j])
swap(arr[2], arr[6])
15 <-> 4
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 12 | 4 | 19 | 16 | 18 | 19 | 15 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^ ^
| | | |
Low | | High
| | |
i j pivot
j = 7
if(arr[j] < arr[pivot])
15 < 13
False
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 12 | 4 | 19 | 16 | 18 | 19 | 15 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^ ^ ^
| | |
Low | High
| |
i pivot
|
j
Terminate the Loop since j become equal to high.
The correct position of the pivot would be the (i+1)
so swap the positoins of (i+1) and pivot
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 7 | 12 | 4 | 13 | 16 | 18 | 19 | 15 | 19 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7 8
^
|
pivot point
All elements left to it are smaller than it.
while to its right are larger or equal to it.All Elements left to pivot point are smaller while that of right of it are larger or equal to it.
Recursively do the same on the left and right subarray
+-----+-----+-----+
left subarry = | 7 | 12 | 4 |
+-----+-----+-----+
0 1 2
+-----+-----+-----+-----+-----+
right subarray = | 16 | 18 | 19 | 15 | 19 |
+-----+-----+-----+-----+-----+
4 5 6 7 8Code
#include <iostream>
#include <vector>
// Partition function to arrange elements around a pivot
// All elements less than the pivot are moved to its left, and those greater to its right
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // Choose the last element as the pivot
int i = low - 1; // Index of smaller element
// Loop to arrange elements based on the pivot value
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // If the current element is smaller than the pivot
i++; // Increment index of smaller element
std::swap(arr[i], arr[j]); // Swap the current element with the element at index i
}
}
// Place the pivot in the correct position by swapping
std::swap(arr[i + 1], arr[high]);
return i + 1; // Return the index of the pivot
}
// Recursive QuickSort function
// Sorts the array by dividing it into subarrays around the pivot element
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
// Find the pivot position
int pi = partition(arr, low, high);
// Recursively apply QuickSort to elements before and after the pivot
quickSort(arr, low, pi - 1); // Sort the left subarray
quickSort(arr, pi + 1, high); // Sort the right subarray
}
}
// Utility function to print elements of an array
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl; // Print a new line after the array
}
int main() {
// Initial array to be sorted
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
int n = arr.size();
// Display the original array
std::cout << "Original array: ";
printArray(arr);
// Sort the array using QuickSort
quickSort(arr, 0, n - 1);
// Display the sorted array
std::cout << "Sorted array: ";
printArray(arr);
return 0;
}
Complexity Analysis
Time Complexity: O(n ^ 2)
- It has an average and best-case time complexity of
O(n log n) - It has worst case time complexity of
O(n ^ 2)
Space Complexity: O( log n)
- Due to the recursive call stack.