3. Quick Sort #

Created Wednesday 01 January 2020

Step 1: Create two phases one either side, one with all elements less than or equal to the pivot. Till both writing heads are equal. How?

• Count the number of elements less(strictly) than pivot_value
• swap(pivot, arr[n_smaller])
• initialize i = 0, j = size-1.
  1. if(arr[i]<arr[n_smaller]) i++;
  2. if(arr[j]<=arr[n_smaller]) j–; // = here coz we need to be strict
  3. if(arr[i]>=arr[n_smaller] && arr[j] < arr[n_smaller]). swap(A[i], A[j]); i++, j–;
• As QS is a tail recursion. We call QS after the partition function.
  • Note that the n_smaller is a sorted position. Avoid it in the function call.
  • Call qs on all before n_smaller.
  • Call qs on all after n_smaller.

Quick Sort