Searching & Sorting
Insertion Sort
Algorithm · Starter
Level: StarterSort First
Watch it run
5
2
8
1
9
3
Step 1 of 19
Insertion sort: grow a sorted section on the left. Take the next value and slide it left until it fits.
Complexity
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Insertion sort | n | n2 | n2 | 1 | Yes |
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
Code
import Sort from '../Sort';
export default class InsertionSort extends Sort {
sort(originalArray) {
const array = [...originalArray];
// Go through all array elements...
for (let i = 1; i < array.length; i += 1) {
let currentIndex = i;
// Call visiting callback.
this.callbacks.visitingCallback(array[i]);
// Check if previous element is greater than current element.
// If so, swap the two elements.
while (
array[currentIndex - 1] !== undefined
&& this.comparator.lessThan(array[currentIndex], array[currentIndex - 1])
) {
// Call visiting callback.
this.callbacks.visitingCallback(array[currentIndex - 1]);
// Swap the elements.
[
array[currentIndex - 1],
array[currentIndex],
] = [
array[currentIndex],
array[currentIndex - 1],
];
// Shift current index left.
currentIndex -= 1;
}
}
return array;
}
}References
Practice
Sort First
- Contains DuplicateEasy
- Valid AnagramEasy
- Meeting RoomsEasy
- Merge Sorted ArrayEasy
- Sort ColorsMedium
- Largest NumberMedium
- H-IndexMedium
- Wiggle Sort IIMedium
- Sort an ArrayMedium
- Custom Sort StringMedium
- Insertion Sort ListMedium
- Maximum GapHard
- Count of Smaller Numbers After SelfHard
Spotted a mistake or something unclear? Report it on GitHub.