-
Slow sorting algorithms
- O(n), O(n2)...
- Selection Sort
- Bubble sort,
- Insertion sort
- All are O(n2)
-
Searching algorithms
- Linear Search, O(n)
- Binary Search, O(log[n])
-
Binary search algorithm sketch
- Find the mid point between the bounds
- Compare the midpoint with the key (<, ==, >)
- Adjust the bounds (if needed)
- Iterate (if needed)
-
Why is binary search fast?
- The search area is reduced by half each time
- log(n)
-
Selection sort sketch
- Start at the first index
- Scan the array for any values smaller than index
- Swap when appropriate
- Iterate the index and repeat
-
Fast sorting algorithms
- Quicksort
- Merge Sort
- Heap Sort
-
Merge Sort Sketch
- Recursively split the array in to halves and sub-halves
- Create a temporary array of equal size
- Combine the halves by placing the smaller elements into the temp array first
- Copy any remaining elements
- Copy everything back into the initial array
- Recursive process
|
|
