Meaningthe sorting of selection (Selection Sort) It is to find the minimum value in the array element, and move this value to the beginning of array. It is necessary to make a reservation, that can be called in this case “the beginning” array (found where the minimum value moves).
“Begining” algorithm Selection sorting with each step loop is shifted towards the tail of the array. Therefore, in the first iteration of the loop, found the minimum value is swapped with the value zero in the cell array. In the second iteration, “begining” already will point to the next (first) cell, and so on.
In fact it turns out a simple swapping of cell values array. When such an exchange does not need the shift values (overwrite) all elements of the array, to assign a minimum value in the appropriate cell. That is, the algorithm Selection sorting It does not require additional memory. Overwrite values occurs immediately after finding the minimum value in an array.
The program code is quite simple, and does not require any special descriptions:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <iostream> using namespace std; int main() { const int N = 10; int a[N] = { 1, 25, 6, 32, 43, 5, 96, 23, 4, 55 }; int min = 0; // для записи минимального значения int buf = 0; // для обмена значениями /*********** Начало сортировки **************/ for (int i = 0; i < N; i++) { min = i; // запомним номер текущей ячейки, как ячейки с минимальным значением // в цикле найдем реальный номер ячейки с минимальным значением for (int j = i + 1; j < N; j++) min = ( a[j] < a[min] ) ? j : min; // cделаем перестановку этого элемента, поменяв его местами с текущим if (i != min) { buf = a[i]; a[i] = a[min]; a[min] = buf; } } /*********** Конец сортировки **************/ for (int i = 0; i < N; i++) //Вывод отсортированного массива cout << a[i] << '\t'; cout << endl; } |
Role “beginning” it plays a counter i the outer loop. At each step, the value of the element, which counts the number of the variable, considered to be minimal. nested loop spends pass through the tail of the array, calculating the number of cells of the array with the minimum value (string 18 – ternary statement).
If, after a nested loop variable min not changed, means the whole array of tail, that is processed, no minimum value, and the element “beginning” it remains in place. Otherwise – value change places with those found.
Tail processed array with each passage loop decreases and when it reaches the end of the array, he (array) will have sorted. The algorithm Selection sorting stop.
This is a great short video on the computer with the analysis the sorting of selection (Selection Sort):
Also read our following lessons devoted to sorting algorithms: bubble sorting and shaker sorting array.
Thank you! Very clearly and accurately set forth the sorting algorithm.
Thank you!