12.Insertion sort
12 May 2020 | Data structure_1
Introduction
- Insertion sort is another take on sorting elements one at a time. This algorithm sorts much like a human being would sort cards.
Why is it Important?
- Insertion sort is another important sorting algorithm that is easy to follow along with. It is the next sort that is typically covered in a Computer Science curriculum.
Lesson Notes
- Insertion sort works similar to that of selection sort, in that it has a sorted and unsorted portion. Instead of finding the minimum in the unsorted portion, it takes the closest number to the unsorted portion and inserts it in to the sorted portion. (Hence the name, insertion sort)
-
So, in the example above, it begins by making the 9 the first member of the sorted subarray. It then looks to the element that is to the right of the sorted subarray. In this case it is the number 7.
-
It grabs this number and inserts it in to the sorted portion. Since it is less than 9, it inserts it behind the 9.
-
Our sorted portion is now 2 big. We then take the next number that is to the right of the sorted portion. This is the 6. We insert that to the left of the 7, as 6 is less than 7. Our sorted portion is now 3 large. We look at the next number which is a 15. This number however is the largest number in the array, so we just keep it where it’s at and move to the next number. We continue this until the array is sorted.
-
This algorithm, although smarter than the other two, is still about the same magnitude of run time. The best case scenario is better than that of selection sort, as if the number to the right of the sorted subarray is larger than the entire sorted array, then it just moves the sorted array over to fill this number. It then just moves on. If the entire array comes in sorted, then it just does 1 pass through the entire array and returns that it is sorted.
-
Best Time: Ω(n) : If the array comes in sorted, it can do just one pass to figure this out. This makes it’s best case scenario, an already sorted array, run at n time.
-
Average Time: Θ(n^2) : The average time of this is similar to that of selection sort. On average we have to search the array 1 less time each iteration. So the run time is generally around n(n-1)/2. This means that It will simplify to (n^2-n)/2 which means it will be n^2.
-
Worst Time: O(n^2) : This is when the array is reverse sorted. The array will have to insert and swap backwards for every single number in the array, making it have to make n operations, for the n sized array. In other words n*n which is n^2.
Introduction
- Insertion sort is another take on sorting elements one at a time. This algorithm sorts much like a human being would sort cards.
Why is it Important?
- Insertion sort is another important sorting algorithm that is easy to follow along with. It is the next sort that is typically covered in a Computer Science curriculum.
Lesson Notes
- Insertion sort works similar to that of selection sort, in that it has a sorted and unsorted portion. Instead of finding the minimum in the unsorted portion, it takes the closest number to the unsorted portion and inserts it in to the sorted portion. (Hence the name, insertion sort)
-
So, in the example above, it begins by making the 9 the first member of the sorted subarray. It then looks to the element that is to the right of the sorted subarray. In this case it is the number 7.
-
It grabs this number and inserts it in to the sorted portion. Since it is less than 9, it inserts it behind the 9.
-
Our sorted portion is now 2 big. We then take the next number that is to the right of the sorted portion. This is the 6. We insert that to the left of the 7, as 6 is less than 7. Our sorted portion is now 3 large. We look at the next number which is a 15. This number however is the largest number in the array, so we just keep it where it’s at and move to the next number. We continue this until the array is sorted.
-
This algorithm, although smarter than the other two, is still about the same magnitude of run time. The best case scenario is better than that of selection sort, as if the number to the right of the sorted subarray is larger than the entire sorted array, then it just moves the sorted array over to fill this number. It then just moves on. If the entire array comes in sorted, then it just does 1 pass through the entire array and returns that it is sorted.
-
Best Time: Ω(n) : If the array comes in sorted, it can do just one pass to figure this out. This makes it’s best case scenario, an already sorted array, run at n time.
-
Average Time: Θ(n^2) : The average time of this is similar to that of selection sort. On average we have to search the array 1 less time each iteration. So the run time is generally around n(n-1)/2. This means that It will simplify to (n^2-n)/2 which means it will be n^2.
-
Worst Time: O(n^2) : This is when the array is reverse sorted. The array will have to insert and swap backwards for every single number in the array, making it have to make n operations, for the n sized array. In other words n*n which is n^2.
