Insertion sort: Difference between revisions
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
Insertion sort is | Insertion sort is an in-place sorting algorithm that goes one element at a time. | ||
In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the | In the insertion sort algorithm, we call the first element of the array "sorted" and the other elements are called "unsorted". Then, we look for the first "unsorted" element. If the first "unsorted" element is not bigger than the rightmost "sorted" elements, the algorithm just swaps downward that element with the rightmost "sorted" element until it is in the right position and mark it as "sorted", and so on. | ||
To implement the insertion sort algorithm efficiently, the array should implemented | To implement the insertion sort algorithm efficiently, the array should implemented using a linked list. | ||
The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n<sup>2</sup>). | The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n<sup>2</sup>). | ||
| Line 14: | Line 14: | ||
|- | |- | ||
|https://www.youtube.com/watch?v=kU9M51eKSX8 | |https://www.youtube.com/watch?v=kU9M51eKSX8 | ||
|- | |||
|https://www.youtube.com/watch?v=OGzPmgsI-pQ | |||
|} | |} | ||
Latest revision as of 06:31, 7 June 2018
Insertion sort is an in-place sorting algorithm that goes one element at a time.
In the insertion sort algorithm, we call the first element of the array "sorted" and the other elements are called "unsorted". Then, we look for the first "unsorted" element. If the first "unsorted" element is not bigger than the rightmost "sorted" elements, the algorithm just swaps downward that element with the rightmost "sorted" element until it is in the right position and mark it as "sorted", and so on.
To implement the insertion sort algorithm efficiently, the array should implemented using a linked list.
The worst-case scenario is when that algorithm is used on a reverse ordered array. Each element should be shifted to other side of the array. The complexity is O(n2).
The best-case scenario is when the algorithm is used on a sorted array. There is O(n) comparisons.
Resources
| https://www.youtube.com/watch?v=kU9M51eKSX8 |
| https://www.youtube.com/watch?v=OGzPmgsI-pQ |