Insertion sort: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the next element. If the next element is not bigger than the current element, the algorithm just shifts downward that element before the current element until it is in the right position and mark it as "sorted", and so on. | In the insertion sort algorithm, we call the first element of the array "sorted". Then, we look for the next element. If the next element is not bigger than the current element, the algorithm just shifts downward that element before the current 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>). | ||
Revision as of 06:15, 5 June 2018
Insertion sort is a 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 next element. If the next element is not bigger than the current element, the algorithm just shifts downward that element before the current 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 |