Shifting
- Algorithms course
- Beginner
- Lesson 30/80
- 4 min
Shift elements right until the correct spot is found.
Full insertion sort
Full insertion sort uses an outer loop from 1 to n-1, performing shift-and-insert for each element.
At each outer loop step, the sorted part grows by one and the new element is placed in its correct position.
Best case
Insertion sort's best case is O(n) when the array is already sorted. In this case, the inner while loop never runs.
The worst case (reverse sorted array) is O(n^2) because the entire sorted part is shifted for each element.
Practice Insertion sort
Write insertion_sort(arr). Place each element in its correct position. Print [1, 2, 3, 4, 5, 6] with print(insertion_sort([5, 2, 4, 6, 1, 3])).
Starter code
def insertion_sort(arr):
# Sort the arraySample solution
def insertion_sort(arr):
# Sort the array
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_sort([5, 2, 4, 6, 1, 3]))Expected output
[1, 2, 3, 4, 5, 6]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Inner loop
Shifting uses a ____ loop.Shifting uses a while loop.Explanation: while is right.
2 Shifting: match the terms
| Term | Meaning |
|---|---|
Outer loop |
1 to n-1 |
Inner while |
Shifts |
Best |
O(n) |
Worst |
O(n^2) |
3 What is insertion sort in the best case?
- O(n) Correct answer
- O(n log n)
- O(n^2)
- O(1)
Explanation: The best case is O(n).