Quick Sort Algorithm Explanation
Quick Sort is a highly efficient and widely used sorting algorithm that
follows the divide and conquer approach. It works by selecting a pivot
element from the array and partitioning the other elements into two sub-
arrays, according to whether they are less than or greater than the pivot.
Then, it recursively sorts the sub-arrays.
Steps of the Quick Sort Algorithm:
1. Select a Pivot: Choose an element from the array to be the pivot.
There are different strategies for choosing a pivot, such as picking
the first element, the last element, a random element, or the
median element.
2. Partitioning: Rearrange the array such that elements less than the
pivot are on the left, elements greater than the pivot are on the
right, and the pivot is placed in its correct position. This step is
called partitioning.
3. Recursion: Recursively apply the same steps (select a pivot and
partition) to the sub-arrays on the left and right of the pivot. The
recursion stops when the sub-array has one or zero elements, as it
is already sorted.
Example of Quick Sort:
Let’s sort the following array using the Quick Sort algorithm:
Array: [10, 80, 30, 90, 40, 50, 70]
Step-by-Step Execution:
Step 1: Select the Pivot
Let’s choose the last element as the pivot. Here, the pivot is 70.
Step 2: Partition the Array
We rearrange the elements such that elements less than the pivot (70)
are placed to the left and elements greater than the pivot are placed to
the right. We do this by iterating through the array and comparing each
element to the pivot.
Start with the leftmost element (10) and iterate through the array.
Keep a pointer (i) for elements less than the pivot. Start by setting i
= -1.
As we iterate, if an element is less than 70, we increment i and swap
the elements.
Initial Array: [10, 80, 30, 90, 40, 50, 70]
Iteration:
10 is less than 70, so increment i to 0 and swap 10 with itself.
80 is greater than 70, so do nothing.
30 is less than 70, so increment i to 1 and swap 80 and 30.
90 is greater than 70, so do nothing.
40 is less than 70, so increment i to 2 and swap 80 and 40.
50 is less than 70, so increment i to 3 and swap 90 and 50.
Array after partitioning: [10, 30, 40, 50, 70, 90, 80]
Now, place the pivot 70 at the correct position (index 4 in this case).
Array after placing pivot: [10, 30, 40, 50, 70, 90, 80]
Step 3: Recursively Sort Sub-arrays
The left sub-array is [10, 30, 40, 50] (elements less than 70).
The right sub-array is [90, 80] (elements greater than 70).
We now recursively apply the quick sort algorithm to these sub-arrays.
Sorting Left Sub-array [10, 30, 40, 50]:
Pivot: 50 (last element).
Partitioning: After partitioning, the array becomes [10, 30, 40, 50]
(pivot 50 is already in place).
No further sorting is needed because the left sub-array [10, 30, 40]
is already sorted.
Sorting Right Sub-array [90, 80]:
Pivot: 80 (last element).
Partitioning: After partitioning, the array becomes [80, 90] (pivot
80 is placed at index 0).
The sub-array is now sorted.
Final Sorted Array:
After recursively sorting all sub-arrays, the final sorted array is:
Sorted Array: [10, 30, 40, 50, 70, 80, 90]
Time Complexity of Quick Sort:
Best Case: When the pivot divides the array into two equal halves.
The time complexity is O(nlogn)O(n \log n).
Worst Case: When the pivot is always the smallest or largest
element, causing the recursion depth to be O(n)O(n). In this case,
the time complexity is O(n2)O(n^2).
Average Case: On average, the pivot divides the array reasonably
well, leading to a time complexity of O(nlogn)O(n \log n).
Space Complexity:
The space complexity is O(logn)O(\log n) due to the recursive call stack (if
the pivot divides the array reasonably well).
Conclusion:
Quick Sort is an efficient sorting algorithm with an average time
complexity of O(nlogn)O(n \log n). It works by selecting a pivot element
and partitioning the array around it. Recursively sorting the sub-arrays
results in a sorted array. Although its worst-case time complexity is
O(n2)O(n^2), it performs very well in practice due to good average-case
performance.
