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)

• 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