QuickSort

Principle Idea:

Determine the positioning of one random pivot each time

Place each element to both sides of pivot

Repeat for both sides of pivot

Time Comp:

On average: O(N logN)

Ideally, each call splits the array into left and right of pivot. Calling logN times.

Worst Case: O(N^2)

If you have terrible karma, the pivot might be chosen on one of the ends every time. Ex: 012345 pivot = 0 , 012345 pivot = 1, 012345 pivot = 2 .....

Every element is pivot, one at a time, thus n^2

Space Comp: O(logN) - O(N) call stacks

public class Solution {

  private void swap (int[] array, int i, int j){
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }

  public int[] quickSort(int[] array) {
    if (array == null) return null;

    quickSortHelper(array, 0, array.length - 1);

    return array;
  }

  public void quickSortHelper(int[] array, int left, int right){
    //base case: one element array
    if (left >= right){
      return;
    }

    //choose the pivot
    int pivot = partition(array, left, right); //sorts one element
    quickSortHelper(array, left, pivot - 1);
    quickSortHelper(array, pivot + 1, right);

  }


  public int partition(int[] array, int left, int right) {
    int pivotIndex = pivotIndex(left, right);
    int pivot = array[pivotIndex];

    swap ( array, pivotIndex, right);
    
    int leftBound = left; 
    int rightBound = right - 1; //excluding pivot

    while( leftBound <= rightBound) {
      if (array[leftBound] < pivot) {
        leftBound++; //if l < p, correct placing, incur next
      } else if (array[rightBound] >= pivot) {
        rightBound--; //if r >= p, correct placing, incur next
      } else {
        swap(array, leftBound++, rightBound--); //else both in wrong place, swap
      }
    }
    swap(array, leftBound, right);
    return leftBound; //leftBound ends at pivot
  }


  public int pivotIndex(int left, int right) {
    return left + (int) (Math.random() * (right - left + 1)); 
  }
}

Mistake to watch out for:

after partition, new position of pivot value is on leftBound , not on pivotIndex.