Selection sort
Sorting an array by finding, on each pass, the minimum of the unsorted part and swapping it into its first cell: trace, number of comparisons and swaps, stability.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Selection sort: what is it?
Show the answer
A sort that, on each pass, finds the smallest item of the unsorted part and swaps it with the first cell of that part.
After k passes, the first k cells hold their final values and never move again: the sorted part grows by one cell per pass.
What is the array after the first pass of selection sort on
[6, 2, 9, 1, 5]?[1, 2, 9, 6, 5][2, 6, 9, 1, 5][1, 6, 2, 9, 5][2, 1, 6, 5, 9]
Show the answer
[1, 2, 9, 6, 5]The minimum, 1, is at index 3: it is swapped with cell 0, which held 6. The 6 goes to position 3 and the other cells do not move. Shifting the cells to slide the 1 to the front, instead of swapping, would give
[1, 6, 2, 9, 5].In selection sort, the inner loop starts at index … and looks for the index … of the unsorted part.
Show the answer
In selection sort, the inner loop starts at index i + 1 and looks for the index of the minimum of the unsorted part.
You start from
m = i: cell i is already a candidate, and the loop only compares the following cells witht[m].Pass: what is it?
Show the answer
One full turn of the outer loop of a sort: here, one search for the minimum followed by one swap.
An array of n values takes n − 1 passes: when n − 1 cells are in place, the last one is too.