Sorting, like searching, is a common task in computer programming. Many different Point algorithms have been developed for sorting. This section introduces an intuitive sorting algorithm: selection sort.
Suppose that you want to sort a list in ascending order. Selection sort finds the smallest number in the list and swaps it with the first. It then finds the smallest number remaining and swaps it with the next to first, and so on, until only a single number remains. Figure 7.8 shows how to sort the list {2, 9, 5, 4, 8, 1, 6} using selection sort.
You know how the selection sort approach works. The task now is to implement it in C++. For beginners, it is difficult to develop a complete solution on the first attempt. You may start to write the code for the first iteration to find the smallest element in the list and swap it with the first element, and then observe what would be different for the second iteration, the third, and so on. The insight this gives will enable you to write a loop that generalizes all the iterations.
The solution can be described as follows:
for (int i = 0; i < listSize – 1; i++)
{
select the smallest element in 1ist[i..1istSize-1];
swap the smallest with list[i], if necessary;
// list[i] is in its correct position.
// The next iteration apply on list[i+1..listSize-1]
}
Listing 7.11 implements the solution.
Listing 7.11 SelectionSort.cpp
1 void selectionSort(double list[], int listSize)
2 {
3 for (int i = 0; i < listSize – 1; i++)
4 {
5 // Find the minimum in the list[i..listSize-1]
6 double currentMin = list[i];
7 int currentMinIndex = i;
8
9 for (int j = i + 1; j < listSize; j++)
10 {
11 if (currentMin > list[j])
12 {
13 currentMin = list[j];
14 currentMinIndex = j;
15 }
16 }
17
18 // Swap list[i] with list[currentMinIndex] if necessary;
19 if (currentMinIndex != i)
20 {
21 list[currentMinIndex] = list[i];
22 list[i] = currentMin;
23 }
24 }
25 }
The selectionSort(double list[], int listSize) function sorts any array of double elements. The function is implemented with a nested for loop. The outer loop (with the loop-control variable i) (line 3) is iterated in order to find the smallest element in the list, which ranges from list[i] to list[listSize – 1], and exchange it with list[i] .The variable i is initially 0. After each iteration of the outer loop, list[i] is in the right place. Eventually, all the elements are put in the right place; therefore, the whole list is sorted. To understand this function better, trace it with the following statements:
double list[] = {1, 9, 4.5, 6.6, 5.7, -4.5};
selectionSort(list, 6);
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.