Insertion sort
Sorting an array by taking the items one by one and inserting each in its place in the already sorted part: shifts, the inner loop, the best case on a sorted array and stability.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Insertion sort: what is it?
Show the answer
A sort that takes the items one by one and inserts each in its place in the part to its left, already sorted, by shifting the larger ones.
It is how you sort playing cards in your hand: take the next one and slide it where it belongs, pushing the others aside.
What does this program print? It shows the array after each insertion.
```python
t = [5, 2, 4, 6, 1]
for i in range(1, len(t)):
x = t[i]
j = i - 1
while j >= 0 and t[j] > x:
t[j + 1] = t[j]
j = j - 1
t[j + 1] = x
print(t)`[2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 6, 1],[1, 2, 4, 5, 6][2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 1, 6][2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 1, 6],[1, 2, 4, 5, 6][1, 5, 2, 4, 6],[1, 2, 5, 4, 6],[1, 2, 4, 5, 6],[1, 2, 4, 5, 6]
Show the answer
[2, 5, 4, 6, 1],[2, 4, 5, 6, 1],[2, 4, 5, 6, 1],[1, 2, 4, 5, 6]Inserting 2 shifts the 5. Inserting 4 shifts the 5. Inserting 6 shifts nothing (6 > 5): the array does not change. Inserting 1 shifts the other four. The last output is the sorted array.
In insertion sort, the left part of the array is …; the item to insert is kept in a variable because its cell will be … by a shift.
Show the answer
In insertion sort, the left part of the array is sorted; the item to insert is kept in a variable because its cell will be overwritten by a shift.
Without that copy, the first shift would destroy the value to insert. The last line writes this value into the freed cell.
Shift: what is it?
Show the answer
Copying an item into the neighbouring cell to free the spot where the item to insert will be written.
Each shift removes exactly one inversion, that is, one pair of items in the wrong order: the number of shifts equals the number of inversions in the array.