Insertion Sort, Selection Sort, and Bubble Sort
After learning all about web development since last October, I’ve been feeling a lot more comfortable learning and applying different frameworks. My current weak spot is my understanding of algorithms. This week I’m reviewing three common search algorithms. As I wanted to remember the abstract parts of these algos, I’ve noted down time and space complexity and described the algorithms, but have left implementation out for now.
Insertion Sort
Best Time: O(n)
Worst Time: O(n²)
Space: Constant
- Assume leftmost value is fully sorted.
- from the remaining set of values, take the leftmost value and compare to the already sorted value on the left.
- If the already sorted number is larger, swap the two numbers, otherwise leave it in place, as a sorted value. 2 leftmost values are now sorted.
- Move on to the next value to sort, now the leftmost value of the unsorted portion of the array. Starting with the rightmost value of the sorted portion of the array, compare values, swapping values if the sorted item is smaller than the item currently being sorted
- If the current value being compared is smaller than the value to sort, or if there are no more items to compare the value to be sorted to, then it is in place. Move on to the next value.
- Once every item has been sorted once, the array will be sorted.
This can vary in time, depending on how close to sorted an array already is. In the case of an array that is in sorted order, insertion sort will run on the scale of O(n).
Selection Sort
Best and Worst Time: O(n²)
Space: Constant
Selection Sort is quite straightforward, but not very efficient. On the first pass, the smallest value is found and moved to index 0. The remainder of the unsorted array is then searched for the new minimum, which is placed at index 1, and so on. For an array of n items, his will require n-passes.
Bubble Sort
Average and Worst Case Time: O(n²)
Best Case Time: O(n)
Space: 1
Starting at the rightmost side of the array. Compare the two rightmost values (n-1, n) and if n is smaller, swap the two values. Then compare the values at (n-2, n-1), swapping if n-2 > n-1. In this manner, the smallest value will bubble all the way to the left on the first pass. If an entire pass completes with no swaps, stop immediately, the array is sorted.
Further Reading
Thanks to wikipedia, xybernetics, and the algorithm app for the gifs I’ve used in this article. They are great resources for further information.
