Insertion sort idea
- Algorithms course
- Beginner
- Lesson 29/80
- 4 min
Like sorting cards, insert each element into the sorted left part.
Insertion sort logic
Insertion sort takes each element and places it in its correct position within the sorted part. This is like arranging cards in your hand.
Initially, the first element is considered sorted. Then the second is taken and placed correctly relative to the first. This repeats for all elements.
Shifting
When placing an element, you shift the sorted elements that are larger than it one step to the right. This makes room for the new element.
Shifting moves elements one by one to the right. The new element goes into the freed slot. This involves fewer writes than swapping.
Practice Shift and insert
Write insert_in_place(arr, i). Place arr[i] in the sorted part. Print [1, 2, 3, 5] with print(insert_in_place([1, 3, 5, 2], 3)).
Starter code
def insert_in_place(arr, i):
# Insert in placeSample solution
def insert_in_place(arr, i):
# Insert in place
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
return arr
print(insert_in_place([1, 3, 5, 2], 3))Expected output
[1, 2, 3, 5]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is insertion sort compared to?
- Tree traversal
- Binary search
- Hash computing
- Arranging cards Correct answer
Explanation: It is compared to arranging cards.
2 Sorted part
The first ____ element is considered sorted.The first 1 element is considered sorted.Explanation: 1 is right.
3 Insertion sort idea: match the terms
| Term | Meaning |
|---|---|
Insertion sort |
Place correctly |
Shifting |
Move right |
Sorted part |
At the start |
O(n^2) |
Worst |