Sorting Algorithms
BACK: Growth of Functions
Definitions
- In-Place New memory is never allocated for the algorithm to run. I.e: Insertion sort is in-place, while merge sort is not.
Running Times
Merge Sort
Pseudocode: pg 31, 34. Split the array in half until you are left with arrays of size 1. Since arrays of size 1 are already sorted, we can merge two arrays of size 1 by comparing them. We input two sorted arrays into the \(\text{MERGE}\) function, so we only need to compare parts of the array.
Quick Sort
Pseudocode: pg 171. Pick a pivot point, put all numbers less than the pivot on the left and all the numbers greater than on the right. Call Quick-Sort again on the left array and the right array.
Note: The worst case situation is if the array is already sorted. This depends on how we pick the pivot. Since each recursive call finds the correct place for value and if we pick the last element to be the pivot every time, we’d have to compare every element with each other (\(n^2\))
Heap Sort:
Heap Sort runs in \(\theta(\text{n}lg\text{n})\) and sorts the data in-place. It uses the idea of a heap, another form of data structure that is represented in an array. In a Max-Heap, the array must have the following property (for all \(i\)):
- \(\text{A[}i\text{]}\leq \text{A[}\text{PARENT(}i\text{)]} \rightarrow \text{A[1]} = \text{largest}\).
- Root: \(\text{A[1]}\)
- Parent: \(\lf \frac{i}{2} \rf\)
- Children: \(2n, 2n+1\)
Pseudocode: pg 154, 157, 160. Create a Max Heap. Repeat the following until the array is sorted: Switch the first and last element and consider the size of the array as \(n - 1\) and then call Max-Heapify.
Counting Sort
Pseudocode: pg 195
Radix Sort
Pseudocode: pg 198
Bucket Sort
Pseudocode: pg 201