Lecture 11 - Elementary Sorting

Elementary Sorts

• Bubble Sort
• Selection Sort
• Insertion Sort
• Bucket Sort
• Counting Sort

High-Performance Sorts

• Quick Sort
  • STL Introsort?
• Merge Sort
• Heap Sort

STL sorting with iterators

Size and Sorting

1. Internal Sort
   1. O(1) time random access, file to be sorted fits in memory
2. Indirect Sort
   1. Reorder indices of items, not the items
3. External Sort
   1. items are accessed sequentially, items sorted on disk, too many elements

Basic Building Blocks

• operator<(): compare item A and B
• operator[]: access k-th elt
• swap(): swap A and B
• compswap(): compare A & B, swaps if B is smaller
• mySort(): algorithm/ implementation
• main(): fill an array with numbers, calls sort, checks and prints results

We want:

Memory Efficiency:

1. Sort in place with O(1) extra memory
2. Sort in place, and use pointers or indices (n items need additional n ptrs or indices)
3. Need Ω(n) extra memory

Stability

• Preservation of relative order of same value items
• simple sorts are usually stable
• complex sorts are usually unstable

Non-Adaptive Sort: sequence of operations is always the same, few conditionals

Adaptive Sort: performs diff. sequence of operations depending on input and outcomes of comparisons

Buba Sort

NON ADAPTIVE
void bubble(item a[], int left, int right) {
    for (int i = left; i < right - 1; ++i) {
        for (int j = right - 1; j > i; --j) {
            compswap(a[j - 1], a[j];
        }
    }
} // buba sort

// 1. Comparisons: n^2 / 2
// 2. Swaps: n^2 / 2
// O(n^2) time


ADAPTIVE
void bubble(item a[], int left, int right) {
    for (int i = left; i < right - 1; ++i) {
        bool swapped = false;
        for (int j = right - 1; j > i; --j) {
            if(a[j] < a[j - 1]) {   // STABLE SORT
                swapped = true;
                swap(a[j - 1], a[j];
            }
        }
        if (!swapped) break;
    }
} // buba sort

// 1. Swaps: n (best case)
// 2. Swaps: n^2 /2 swaps average case
// O(n^2) time, Ω(n) time for best case
// Finish quickly if the input array is almost sorted

Selection Sort

NON ADAPTIVE 
void selection(Item a[], int left, int right) {
    for (int i = left; i < right - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < right; ++j) {
            if (a[j] < a[min]) 
                min = j;
        }
        swap(a[i], a[min]);
    }
}  // selection sort

// 1. Comparisons: n^2 / 2
// 2. Swaps: n - 1 (best, average, worst)
// O(n^2) time


ADAPTIVE
void selection(item a[], int left, int right) {
    for (int i = left; i < right - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < right; ++j) {
            if (a[j] < a[min])
                min = j;
        }
        if (min!= i) swap(a[i], a[min]);  // don't swap if item is already in correct position
    }
}

// 1. Comparisons: (n^2 - n) / 2 + (n - 1)
// 2. Swaps: n - 1 (worst)
// 3. Swaps: 0 (best)
// O(n^2) time

Sorts usually involve comparisons and swaps, other methods exist

Insertion Sort

• Consider elts one at a time
• Insert each elt into its proper place among those already considered (sorted/unsorted?)

NON ADAPTIVE
void insertion(Item a[], int left, int right) {
    for (int i = left + 1; i < right; ++i) {
        for (int j = i; j > left; --j) {
            compswap(a[j - 1], a[j]);
}

// 1. Comparisons: n^2 / 2
// 2. Swaps: n^2 / 2
// 3. Swaps: n^2 / 4 average

Improvement 1: Move instead of Swap
Improvement 2: Replace for with while, and remove the break statement
Improvement 3: Eliminate frequent tests with a sentinel


ADAPTIVE
void insertion(Item a[], int left, int right) {
    for (int i = right - 1; i > left; --i) {     // find min item
        compswap(a[i - 1], a[i]);                // put in a[left]
    }
    for (int i = left + 2; i < right; ++i) {
        Item v = a[i];           // v is new item
        int j = i;
        while (v < a[j - 1]) {   // v in wrong location
            a[j] = a[j - 1];     // move = half swap
            --j;
        }
        a[j] = v;
    }
}

// Comparisons: n^2 / 4 average
// Comparisons: n^2 / 2 worst
// Swaps/Moves: n^2 / 4 average
// Swaps/Moves: n^2 / 2 worst
// O(n^2)

Simple sorts (at least buba and insertion) only do well on pre-sorted inputs

Performance Analysis

Non-Comparison Sorts Below

Bucket(Bin)Sort

• O(n) time, but not in-place, so O(n?) memory

void binsort(vector<size_t> &A) {
    vector<vector<size_t>> B(MAX); // bins
    for(auto a: A)
        B[a].push_back(a);
    size_t current = 0;
    for (size_t i = 0; i < MAX; ++i) {
        for (auto item : B[i])
            A[current++] = item;
    }
}

Counting Sort - optimization of bucket sort (adaptive?)

IN PLACE
void in_place_counting_sort(vector<size_t> &A) {
    vector<size_t> C(MAX + 1);
    for (auto a : A)              // Pass 1
        ++C[a];
    int current = 0;
    for (size_t i = 0; i < MAX; ++i) {  // Pass 2?
        for (size_t j = 0; j < C[i]; ++j)   // Pass 3
            A[current++] = i;
}

STL Sort: 2 iterators, 1 optional functor parameter

If a < b, the sort is increasing

a > b (or b < a) produces a decreasing sort order