Quick Sort

This is a very important topic in algorithms and hence I wanted to cover it.

Here is the code for quicksort at github: https://github.com/zcoderz/leetcode/blob/main/src/main/java/sort/QuickSort.java

Quick sort has the below logic:

• Work on a range LOW to HIGH
• Pick a pivot in the range
  • Pivot could be medial of first , last and middle element in the range. Idea is that median of first , last and middle will give a value that will have a high probability of dividing the range between high and low evenly in two halves
• Move the pivot to its correct index in the range between low and high
  • This ensures by definition that the data on left of the pivot index is less than the pivot and that at right of it is greater than it
• Repeat the process recursively for each of sub arrays on left and right of the pivot

Here is the main driver that partitions the pivot into its correct index and recursively repeats for left and right sub arrays:

void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    //get the index which was chosen as pivot and partitioned into its correct place
    int j = partition(arr, lo, hi);
    //repeat for left part of the array
    quickSort(arr, lo, j - 1);
    //repeat for right part of the array
    quickSort(arr, j + 1, hi);
}

Here is the partition method which choses a pivot index and places the value at its correct location in the range from low to high. Look carefully that when i & j cross each other then j by definition must be at the correct slot for the pivot and thus the loop breaks.

int partition(int[] arr, int lo, int hi) {
    int pivot = arr[lo];//better to take pivot as median of hi, mid , lo
    int i = lo + 1;
    int j = hi;
    while (j > i) {
        while (arr[j] > pivot) j--;
        while (arr[i] < pivot) i++;
        if (i >= j) break; //stop when i & j cross
        //per above loop by definition i would be at an index greater than the pivot value
        //and j would be at an index less than the pivot
        swap(arr, i++, j--);
    }
    swap(arr, j, lo); //j represents the index at which the pivot should exist
    return j;
}