> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/sorts/quicksort.md).

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