Sorting Algorithms
| Algorithm | Best Time | Average Time | Worst Time | Worst Space |
|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n^2) | O(log n) |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Tree Sort | O(n log n) | O(n log n) | O(n^2) | O(n) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
Quicksort
- Partition array
- Pick some element to be the pivot element
- Go through array
- If current element is smaller than the pivot,
- Swap with current pointer to end of smaller elements
- Increment pointer
- Swap pivot element with the pointer element
- If current element is smaller than the pivot,
- Quicksort the left and right subarrays (leaving pivot in place).
Notes:
- Recursive
- Not stable sort
Mergesort
- Find midpoint of array, and split into two halves
- Mergesort each half
- Take resulting sorted arrays and merge them together
- Keep pointer to each
- Take smaller value until one array is empty
- Dump remaining array into end of new merged array
Notes:
- Recursive
- Stable
Heapsort
The following uses a max heap, where the array is used like a pseudo tree with the following methods available:
- Parent(i) = floor(i/2)
- Left(i) = 2*i
- Right(i) = 2*i + 1
The only rule in a max heap is that an element’s parent is greater than or equal to (>=) the element. (Min heap is the opposite)
- Build Max Heap out of array
- Starting at the midpoint of the array to the start (index 0),
MAX HEAPIFY():- Get Left and Right children indices of current index
- If Left child is within bounds of the heap, and Left child is bigger than the current element,
- Largest is the Left child
- If Right child is within the bounds of the heap, and Right child is bigger than Largest,
- Largest is the right child
- If Largest is not the current element,
- Swap current element with the largest element
- Run
MAX HEAPIFY()on the current element’s new location (Largest’s old location)
- Starting at the midpoint of the array to the start (index 0),
- Starting at end of array, swap top of heap (biggest element, index 0) with current index i.
- Max Heapify remaining elements (0 -> i - 1)
Notes:
- Not stable
Insertion Sort
- Start at index 0
- While not at end of array
- Get current index value
- Insert it into its correct place in the sorted section of the array
- Shift remaining sorted values down
Mergesort vs Quicksort
While both have similar average times, and quicksort has worse worst case time, quicksort can be faster due to less overhead copying and merging arrays, as it is in place.