Why?
improve search from O(n) to O(log n)
printing in desirable sequence
BubbleSort / Selection Sort / InsertionSort / Heap Sort
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
get pivot out of the way - swap pivot with last
left skip smaller, right skip larger, swap until cross
retrieve pivot
what if element is identical to pivot?
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) {
Begin head = start if head is null or next(head) is null, then return
split_list(head, ll1, ll2) mergeSort(ll1) mergeSort(ll2) start := mergeList(ll1, ll2)End
STL implementations
void sort ( Iterator begin, Iterator end);
void sort ( begin, end, Comparator cmp);
e.g. sort (v.begin(), v.end(), greater<int>());