Lecture 12 - QuickSort

Bubble Sort is only the fastest in edge case where array is sorted (lol), otherwise really bad

Insertion sort - keep growing sorted array to the right, and sort to the left

Insertion Sort (non-adaptive)

• No swapping, just copy a value (sentinel) and change(MOVE) it with the one being compared against
• Break/stop when you find first value that is less than the value you're trying to insert
• Smallest value (so far) should always be to the farthest left, so you can never walk off the end of the array
  • You don't have to worry about while (j>left && v<a[j - 1]) { ... }
• Use a sentinel character

Swapping is a 3-memory operation

Simple sorts compare every pair of elts, and/or move elts one place at a time

Quicksort uses recursion, and partitions

Quicksort uses O(1) additional memory

• Base case: length 0 or 1 array
• Pick elt to partition array, move elts to left or right or elt based on value, then insert elt in correct place (middle-ish)
• Recursively sort LHS and RHS (conquer0
• Range is [left, right)
• Pick just any elt for the pivot, say, the last item

QUICKSORT
void quicksort(int a[], int left, int right) {
    if (left + 1 >= right) return;
    int pivot = partition(a, left, right);
    quicksort(a, left, pivot);      // recurse LHS of pivot
    quicksort(a, pivot + 1, right); // recurse RHS of pivot
}

FINDING MEDIAN
// several ways, but too expensive for a sort

SIMPLE PARTITION
int partition(int a[], int left, int right) {
    int pivot = --right;  // choose pivot

    while(true) { 
        while(a[left] < a[pivot])
            ++left;
        while(left < right && a[right - 1] >= a[pivot]) 
            --right;
        if (left>= right)
            break;
        swap(a[left], a[right - 1]);   // swap left and right pairs until left and right cross
    }
    swap(a[left], a[pivot]);   // move pivot to middle
    return left;
}

ANOTHER PARTITION:
// 1. Choose middle item as pivot
// 2. Swap it with the right end
// 3. Repeat as before
int partition(int a[], int left, int right) {
    int pivot = left + (right - left) / 2;
    swap(a[pivot], a[--right], std::less);  // swap middle item with right end
    pivot = right;    // choose pivot

    // the rest is same as above partition code
    while(true) {
        while(a[left] < a[pivot])
            ++left;
        while(left < right && a[right - 1] >= a[pivot])
            --right;
        if (left>= right)
            break;
        swap(a[left], a[right - 1]); // swap left and right pairs until left and right cross
    }
    swap(a[left], a[pivot]); // move pivot to middle
    return left;
}

Analysis

• Each partition of n elements costs: O(n)

• Worst case: O(n^2), as bad as elementary sorts

• Best case: O(n log n)

• Average case: O(n log n)

• Quicksort is NOT easily made stable

Improvements:

• Sampling to get good pivot, not necessarily median
• Bail out of quicksort and do insertion sort for small k
• Fast insertion pass at the end

Pivot selection can be improved by sampling 3, 5 or so elts (first, middle, last) and getting their median

Stability (look these up)

• Bubble Sort: Stable
  • Only swaps elts if the elts are different valued
• Insertion Sort: Stable
  • While comparing itself, only swap if strictly less than
• Selection Sort: NOT stable
• Heapsort: NOT stable
  • When extracting max elts in heap(sort?), same valued items get reversed in order
• Quicksort: NOT stable
• Mergesort: Stable

How can you make an unstable sort ensure stable output?

• Comparator changing, add further criteria, the index order can be a tiebreaker
• Use std::stable_sort( , , )