Selection sort idea
- Algorithms course
- Beginner
- Lesson 25/80
- 4 min
Find the minimum each round and place it at the front.
Selection sort logic
Selection sort finds the smallest element in the array and places it at the first position, then repeats for the remaining part.
At each step, the smallest is selected from the unsorted part and placed at the end of the sorted part. This builds the sorted array from the start.
Finding the minimum
To find the smallest element, you scan all elements and track the smallest so far. This requires O(n) operations.
Finding the minimum is the building block of selection sort. At each step, a minimum is found and placed in the right position.
Practice Find minimum index
Write find_min_index(arr). Return the index of the smallest element. Print 3 with print(find_min_index([5, 2, 8, 1, 9])).
Starter code
def find_min_index(arr):
# Find minimum indexSample solution
def find_min_index(arr):
# Find minimum index
min_idx = 0
for i in range(1, len(arr)):
if arr[i] < arr[min_idx]:
min_idx = i
return min_idx
print(find_min_index([5, 2, 8, 1, 9]))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What does selection sort do at each step?
- Computes hash
- Swaps neighbors
- Splits array in half
- Finds smallest and places it Correct answer
Explanation: Finds smallest and places it.
2 Minimum index
The smallest element's index is kept in ____.The smallest element's index is kept in min_idx.Explanation: min_idx is right.
3 Selection sort idea: match the terms
| Term | Meaning |
|---|---|
Selection sort |
Pick smallest |
Minimum |
O(n) search |
Swap |
Exchange |
O(n^2) |
Complexity |