sort

Why?

improve search from O(n) to O(log n)

printing in desirable sequence

Simple Sorts O(n²)

BubbleSort / Selection Sort / InsertionSort / Heap Sort

Divide and Conquer Sorts

QuickSort -- choose pivot, partition, recursively sort each partition

• Array is partitioned into two subarrays

• Subarrays are sorted using quicksort (recursion)

• Two sub-arrays are sorted and combined into one array

• Complexity is O(n log n)

• The most popular sorting algorithm for array.... in place sorting, fast (most cases), simple code.

choose pivot - first or last (not a good idea), random (safe), middle (convenient), median (ideal), median-of-three (typical)

partition method

• 1. get pivot out of the way - swap pivot with last

  2. left skip smaller, right skip larger, swap until cross

  3. retrieve pivot

what if element is identical to pivot?

Merge Sort -- divide, sort, merge

• Complexity is always n log n, but it takes a lot of space and/or copying.

• That's why merge sort is mostly used in linked list (re-arrange pointers is easier than copy)

MergeSortArray (A, left, right) {

if (left < right) {

mid = floor((left + right) / 2);

MergeSort(A, left, mid);

MergeSort(A, mid+1, right);

Merge(A, left, mid, right); // merge two sorted sublists

}

}

MergeSortLinkedList (start) {

STL implementations

void sort ( Iterator begin, Iterator end);

void sort ( begin, end, Comparator cmp);

e.g. sort (v.begin(), v.end(), greater<int>());