Swapping
- Algorithms course
- Beginner
- Lesson 27/80
- 4 min
Swap the minimum to the front; count the rounds.
Full selection sort
Full selection sort uses an outer loop for each position; the inner search finds the minimum from that position onward and swaps.
The outer loop goes from 0 to n-2; the inner search goes from i to n-1. At each step, a minimum is found and swapped.
Complexity analysis
Selection sort's complexity is always O(n^2). Best, worst and average cases are the same because all remaining elements are always scanned.
The number of swaps is at most n-1, which is fewer than bubble sort. But the number of comparisons is always n(n-1)/2.
Practice Selection sort
Write selection_sort(arr). Find minimum at each position and swap. Print [11, 12, 22, 25, 64] with print(selection_sort([64, 25, 12, 22, 11])).
Starter code
def selection_sort(arr):
# Sort the arraySample solution
def selection_sort(arr):
# Sort the array
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([64, 25, 12, 22, 11]))Expected output
[11, 12, 22, 25, 64]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Swapping: match the terms
| Term | Meaning |
|---|---|
Outer loop |
0 to n-2 |
Inner search |
i to n-1 |
Swap |
n-1 times |
O(n^2) |
Always |
2 How many comparisons does selection sort make in the best case?
- n
- n(n-1)/2 Correct answer
- 1
- 0
Explanation: Even in the best case, n(n-1)/2 comparisons.
3 Outer loop
The outer loop runs with ____ range(n - 1).The outer loop runs with for i in range(n - 1).Explanation: for i in is right.