Смысл Сортировки выбором (Selection Sort) состоит в поиске минимального значения элемента в массиве, и перемещения этого значения в начало массива. Нужно сразу оговориться, что в данном случае можно назвать “началом” массива (куда перемещается найденное минимальное значение).
“Начало” в алгоритме Сортировка выбором с каждым шагом цикла смещается в сторону хвоста массива. Поэтому на первой итерации цикла, найденное минимальное значение меняется местами со значением в нулевой ячейке массива. На второй итерации “начало” уже будет указывать на следующую (первую) ячейку и так далее.
По факту получается простой обмен местами значений ячеек массива. При таком обмене значениями не нужен сдвиг (перезапись) всех элементов массива, чтобы записать минимальное значение в соответствующую ячейку. То есть алгоритм Сортировка выбором не требует использования дополнительной памяти. Перезапись значений происходит сразу после нахождения минимального значения в массиве.
Код программы весьма прост, и не требует каких-то особых описаний:
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; } |
Роль “начала” здесь играет счетчик i внешнего цикла. На каждом шаге значение элемента, номер которого отсчитывает эта переменная, считается минимальным. Вложенный цикл проводит проход по хвосту массива, вычисляя номер ячейки массива с минимальным значением (строка 18 – тернарный оператор).
Если после прохода вложенным циклом переменная min не изменилась, значит из всего хвоста массива, который обрабатывается, минимального значения нет, и элемент “начала” остается на своем месте. Иначе – значение меняется местами с найденным.
Хвост обрабатываемого массива с каждым проходом циклов уменьшается и когда достигнет конца массива, он (массив) окажется уже отсортированным. Работа алгоритма Сортировка выбором прекратится.
Вот отличное короткое видео по информатике с разбором Сортировки выбором (Selection Sort):
Прочтите также наши следующие уроки посвященные алгоритмам сортировки: пузырьковая сортировка и шейкерная сортировка массива.
Спасибо! Очень понятно и точно изложен алгоритм сортировки.
Спасибо!