Sorting Algorithms: Buble, Insertion, and Selection Sort(Part 1)
Let’s start with a quick overview:
- Bubble Sort: step through list comparing adjacent elements, and swapping them is they are in the wrong order, good if data is already partially sorted
- Insertion Sort: inserts numbers from the unsorted list to the sorted list one at a time, good for online data (live data)
- Selection Sort: iterating through the array, finding the smallest value and swapping it with the first unsorted number in the list, not efficient, but it is simple
Bubble Sort: we repeatedly step through the list, comparing adjacent elements and swapping them if they are in the wrong order. In this example we would swap 15 with 3, then 15 with 2, and continue until 15 is at the end of the list. We will continue to do the same with all values until we have an ordered list. Bubble sort has an average time complexity of O(n²).
Insertion Sort: creates a sorted list by inserting numbers one at a time from the original list. Insertion sort runs in O(n²), or quadratic time (in the worst case).
First we separate our list into sorted, and non sorted. Index 0 will initially be the only sorted value, all following indices will be part of the unsorted list.
We then will check the first value (key) in the non sorted list, and insert it in the sorted list, by swapping it to the left of any larger values.
Step by step:
- 3 is less than 15, so we move 3 to the left of 15
- Now that 3 is in the sorted list we move on to 2. 2 is less than 15, so we move 2 to the left of 15. 2 is less than 3, so we move it to the left of 3.
- Now that 2 is in the sorted list we move on to 9. 9 is less than 15, so we move it to the left. 9 is greater than 3, so it stays.
- Once 9 is in the sorted list we continue to follow the same procedure until we get a folly sorted list as you can see to the below.
Selection Sort: iterating through the array, finding the smallest value (that has not been sorted) and swapping it with the first unsorted number in the array. Selection sort has a O(n²) time complexity.
Overview: here we start with 15, when iterating through the array 2 is the smallest number. For that reason 2 and 15 are swapped. Then we move on to 3, there are no smaller numbers in the array so 3 does not move. Then we move on to 15, 5 is the smallest number in the unsorted portion of the array, so we swap the two. We continue to do this until all values are sorted.