Sorting
Calculate the permuation that orders the elements in an array.
Insertion sort #
Idea: Start with one element, keep adding new elements and swap them until they have the right position.
- Worst case: $\mathcal{O}(n^2)$
- Base case: $\mathcal{O}(n)$
- Average case: $\mathcal{O}(n^2)$
- In-place
Merge sort #
Uses the recursive divide and conquer approach:
- Divide the problem into subproblems
- Conquer the subproblems by recursion
- Combine the solutions of the subproblems into the global solution
Idea: Split array into two parts which get sorted recursively (devide/conquer) and merge the two sorted subarrays into a full array (combine)
- Time complexity: $\Theta(n \lg n)$
- Needs additional memory
Quicksort #
Heap sort #
- Construct a heap in linear time
- Get items from the top of the heap untill it is empty