7.2. Selection sort¶
The selection sort improves on the bubble sort by making only one exchange for every pass through the first part of the vector. We will call this a step. In order to do this, a selection sort looks for the largest value as it makes a partial pass and, after completing the partial pass, places it in the proper location, ending the step. As with a bubble sort, after the first step, the largest item is in the correct place. After the second step, the next largest is in place. This process continues and requires \(n-1\) steps to sort n items, since the final item must be in place after the \((n-1)\) step.
Selection sort: the first pass
Card 1: Compare the candidate 54 with 26.
Start with 54 as the largest value seen so far. The outlined cells show the current candidate and the value being compared. Since 26 is less than 54, keep 54 as the candidate. Leave every value in place until the search is complete.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“54” and “26” are highlighted.
Card 2: Compare the candidate 54 with 93.
Since 93 is greater than 54, remember its position as the new candidate. Finding a larger value changes the candidate without exchanging any items.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“54” and “93” are highlighted.
Card 3: Compare the candidate 93 with 17.
The candidate is now 93. Since 17 is smaller, keep 93 as the candidate and continue the search.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“93” and “17” are highlighted.
Card 4: Compare the candidate 93 with 77.
Since 77 is less than 93, the candidate remains 93. The array still has its original order.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“93” and “77” are highlighted.
Card 5: Compare the candidate 93 with 31.
Since 31 is less than 93, keep 93 as the candidate. Continue checking the remaining values.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“93” and “31” are highlighted.
Card 6: Compare the candidate 93 with 44.
Since 44 is less than 93, keep 93 as the candidate. No values have been exchanged during the search.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“93” and “44” are highlighted.
Card 7: Compare the candidate 93 with 55.
Since 55 is less than 93, keep 93 as the candidate. Only the last value remains to be checked.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“93” and “55” are highlighted.
Card 8: Compare the candidate 93 with 20.
Since 20 is less than 93, the candidate remains 93. All eight comparisons are complete, so 93 is the largest value in the array.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“93” and “20” are highlighted.
Card 9: Exchange 93 with the last value, 20.
The search is complete. Exchange the largest value, 93, with 20 in the last cell. This single swap puts 93 in its final position.
Text description
Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.
“93” and “20” are highlighted.
Card 10: The first pass is complete; 93 is in its final position.
Eight comparisons and one exchange have placed 93 at the end. The outlined final cell will not be searched again. The remaining eight values still need to be sorted.
Text description
Array with 9 cells. From left to right: “54”, “26”, “20”, “17”, “77”, “31”, “44”, “55”, and “93”.
“93” is highlighted.
Selection Sort
On each step, the largest remaining item is selected and then placed in
its proper location. If the 3 largest values are [55, 77, 93], then
the first pass places 93, the second pass places 77, the third places 55,
and so on.
Yellow marks the current candidate, red marks the value being compared, teal marks the boundary for the current step, and gray marks values already sorted.
Run It
1#include <iostream>
2#include <utility>
3#include <vector>
4using std::vector;
5
6vector<int> selection_sort(vector<int> data) {
7 for (int slot = data.size()-1; slot >= 0; --slot) {
8 int largest = 0; // location of the largest element
9 for (int location = 1; location < slot+1; location++) {
10 if (data[location] > data[largest]) {
11 largest = location;
12 }
13 }
14 std::swap(data[slot], data[largest]);
15 }
16 return data;
17}
18
19int main() {
20 vector<int> data = {54, 26, 93, 17, 77, 31, 44, 55, 20};
21 for (const auto& value: selection_sort(data)) {
22 std::cout << value << ' ';
23 }
24 std::cout << '\n';
25 return 0;
26 }
7.2.1. Selection sort analysis¶
You may see that the selection sort makes the same number of comparisons as the bubble sort and is therefore also \(O(n^{2})\). Like the bubble sort, the selection sort makes no exchanges when the data is already sorted ascending. In other cases selection sort generally makes fewer exchanges than bubble sort when presented with the same data. Due to the smaller number of exchanges, the selection sort typically executes faster than bubble sort.
Self Check
Q1
Suppose you have the following vector of numbers to sort: [11, 7, 12, 14, 19, 1, 6, 18, 8, 20] which vector represents the partially sorted (ascending) vector after three steps of selection sort?
More to Explore