Summary - Insertion sort
- Algorithms course
- Beginner
- Lesson 32/80
- 4 min
Implement insertion sort in a mini task.
Summary - Insertion sort
In this group you learned insertion sort's logic, shifting, full sorting and advantages. Complexity is O(n^2), best case O(n).
Insertion sort is preferred for nearly sorted arrays and small data. It sorts in-place and does few writes.
Practice Full insertion sort
Write insertion_full(arr). Sort with for and while. Print [1, 1, 2, 3, 4, 5, 6, 9] with print(insertion_full([3, 1, 4, 1, 5, 9, 2, 6])).
Starter code
def insertion_full(arr):
# Fully sortSample solution
def insertion_full(arr):
# Fully sort
for i in range(1, len(arr)):
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(insertion_full([3, 1, 4, 1, 5, 9, 2, 6]))Expected output
[1, 1, 2, 3, 4, 5, 6, 9]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Insertion sort: match the terms
| Term | Meaning |
|---|---|
Insertion sort |
Place correctly |
Shifting |
Move right |
Best |
O(n) |
In-place |
No extra memory |
2 Insertion sort
Question
Insertion sort places each element in the ____ part.
Answer
Insertion sort places each element in the sorted part.Explanation: sorted is right.
3 How long does insertion sort take on nearly sorted arrays?
- O(n^2)
- O(1) Correct answer
- O(n log n)
- O(n)
Explanation: On nearly sorted arrays it is O(n).