Quick Sort
Quick Sort
- Is one of the most efficient sorting algorithms.
- Is based on the divide and conquer approach.
- Successively divides the problem into smaller parts until the problems become so small that they can be directly solved.
Quick Sort Algorithm
QuickSort(low,high)
1. If (low > high):
Return.
2. Set pivot = arr[low].
3. Set i = low + 1.
4. Set j = high.
5. Repeat step 6 until i > high or arr[i]> pivot.
// Search for an element greater than the pivot.
6. Increment i by 1.
7. Repeat step 8 until j < low or arr[j] < pivot.
//Search for an element smaller than pivot
8. Decrement j by 1.
9. If i < j:
// If greater element is on the left of
//smaller element
Swap arr[i] with arr[j].
10. If i <= j:
Go to step 5. // Continue the search
11. If low < j:
Swap arr[low] with arr[j].
//Swap pivot with last element in first part of the list
Determining the Efficiency of the Quick Sort Algorithm
- The total time taken by this sorting algorithm depends on the position of the pivot value.
- If the first element is chosen as the pivot, it leads to a worst case efficiency of O(n2).
- The worst case occurs when the list is already sorted.
- In this case, the total number of comparisons is:
Number of comparisons
= n + (n – 1) + (n – 2) + .. + 2 + 1
= n(n – 1)/2
= O(n2)
- If you select the median of all values as the pivot, the efficiency will be O(n log n).