# Quick sort

## 1.Quick sort

* divide and conquer algorithm
  * The partition is not based on the length or an artificial index, it's based on a pivot
* The pivot is an element from the list
  * The list is partitioned with all elements smaller than the pivot on one side and larger than the pivot on the other
* The pivot partition is applied to all sub-lists till the list is sorted

## 2.Code

1. The "partition" method which finds a pivot and moves elements to before or after the pivot
2. The "quicksort" method which does the recursive call to sort the sub-list

* partition method

```
//Low and high specify indices which determin what portion of the list we're working on
public static int partition(int[] listToSort, int low, int high) {
    //Choose a pivort to partition the list
    int pivot = listToSort[low];
    int l = low;
    int h = high;
    //The loop continues so long as the indices don't cross one another art the center
    //Moving from either end of the list towards the center we compare the elements to the pivort
    while (l < h){
        //找出大於pivort的index
        while (listToSort[l] <= pivort && l < h) {
            l++;
        }
        //找出小於pivort的index
        while (listToSort[h] > pivort) {
            h--;
        }
        //Elements larger than the pivot are swapped to after the pivot 
        //and smaller elements move before the pivot
        if (l > h) {
            swap(listToSort, l, h);
        }
    }
    //Swap the pivot element to the correct position in the list
    swap(listToSort, low, h);
    print(listToSort);
    return h;
}
```

* quicksort method

```
public static void quickSort(int[] listToSort, int low, int high) {
    //Stop the sort if the lower index is not actually lower than the higher index
    if (low >= high) {
        return;
    }
    //Find the pivot
    int pivotIndex = partition(listToSort, low, high);
    //Quicksort the portion of the list on either side of the pivot
    quickSort(listToSort, low, pivotIndex - 1);
    quickSort(listToSort, pivotIndex + 1, high);
}
```

## **3.Complexity**

* The average case complexity of quick sort is O(NLogN)&#x20;
* The algorithm is not adaptive
* It takes O(LogN) extra space for call stack in the recursion
* The worst case for space complexity could be O(N): 依實作出來的層數覺定
* It is a stable sort