#### 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).