Summary - Selection sort
- Algorithms course
- Beginner
- Lesson 28/80
- 4 min
Implement selection sort in a mini task.
Summary - Selection sort
In this group you learned selection sort's logic, finding minimum, swapping and full sorting. Complexity is always O(n^2).
Selection sort does few swaps (n-1) but many comparisons (n^2). It is simple but slow.
Practice Selection sort step
Write selection_step(arr, i). Find minimum after i and swap with arr[i]. Print [1, 3, 2] with print(selection_step([3, 1, 2], 0)).
Starter code
def selection_step(arr, i):
# Do one stepSample solution
def selection_step(arr, i):
# Do one step
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_step([3, 1, 2], 0))Expected output
[1, 3, 2]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Selection sort: match the terms
| Term | Meaning |
|---|---|
Selection sort |
Pick smallest |
Minimum |
Find index |
Swap |
Exchange |
O(n^2) |
Always |
2 Selection sort
Question
Selection sort finds the ____ at each step.
Answer
Selection sort finds the smallest at each step.Explanation: smallest is right.
3 How many swaps does selection sort make?
- n^2
- n log n
- 1 Correct answer
- n-1
Explanation: At most n-1 swaps.