Выбор

Смысл Сортировки выбором (Selection Sort) состоит в поиске минимального значения элемента в массиве, и перемещения этого значения в начало массива. Нужно сразу оговориться, что в данном случае можно назвать «началом» массива (куда перемещается найденное минимальное значение). «Начало» в алгоритме Сортировка выбором с каждым шагом цикла смещается в сторону хвоста массива. Поэтому на первой итерации цикла, найденное минимальное значение меняется местами со значением в нулевой ячейке массива. На второй итерации «начало» уже будет указывать на следующую (первую) ячейку и так далее.

По факту получается простой обмен местами значений ячеек массива. При таком обмене значениями не нужен сдвиг (перезапись) всех элементов массива, чтобы записать минимальное значение в соответствующую ячейку. То есть алгоритм Сортировка выбором не требует использования дополнительной памяти. Перезапись значений происходит сразу после нахождения минимального значения в массиве.

Код программы весьма прост, и не требует каких-то особых описаний:

#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;

}

Роль «начала» здесь играет счетчик i внешнего цикла. На каждом шаге значение элемента, номер которого отсчитывает эта переменная, считается минимальным. Вложенный цикл проводит проход по хвосту массива, вычисляя номер ячейки массива с минимальным значением (строка 18 — тернарный оператор). Если после прохода вложенным циклом переменная min не изменилась, значит из всего хвоста массива, который обрабатывается, минимального значения нет, и элемент «начала» остается на своем месте. Иначе — значение меняется местами с найденным.

Хвост обрабатываемого массива с каждым проходом циклов уменьшается и когда достигнет конца массива, он (массив) окажется уже отсортированным. Работа алгоритма Сортировка выбором прекратится.