Search

# Quick Sort

Last updated Mar 9, 2023

Like Merge Sort, Quick Sort is Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot.

The key process in quickSort is partition(). The target of parition is, given an array and an element x of an array as the pivot, put x at the correct position in a sorted array and smaller elements before x, and put all greater elements after x. All this should be done in linear time. ### # Pseudo-code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  /* low  –> Starting index,  high  –> Ending index */ quickSort(arr[], low, high) {     if (low < high) {         /* pi is partitioning index, arr[pi] is now at right place */         pi = partition(arr, low, high);         quickSort(arr, low, pi – 1);  // Before pi         quickSort(arr, pi + 1, high); // After pi     } } 

and the pseudo code for partition():

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ partition (arr[], low, high) {     // pivot (Element to be placed at right position)     pivot = arr[high];       i = (low – 1)  // Index of smaller element and indicates the      // right position of pivot found so far     for (j = low; j <= high- 1; j++){         // If current element is smaller than the pivot         if (arr[j] < pivot){             i++;    // increment index of smaller element             swap arr[i] and arr[j]         }     }     swap arr[i + 1] and arr[high])     return (i + 1) }