- 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
- If you select the median of all values as the pivot, the efficiency will be O(n log n).