сенссортування вибором (вибір Сортування) полягає у пошуку мінімального значення елемента в масиві, і переміщення цього значення в початок масиву. Потрібно відразу обмовитися, що в даному випадку можна назвати “початком” массива (куди переміщається знайдене мінімальне значення).
“старт” в алгоритмі Сортування вибором з кожним кроком циклу зміщується в бік хвоста масиву. Тому на першій ітерації циклу, знайдене мінімальне значення міняється місцями зі значенням в нульовий осередку масиву. На другий ітерації “старт” вже буде вказувати на наступну (першу) осередок і так далі.
За фактом виходить простий обмін місцями значень осередків массива. При такому обміні значеннями не потрібен зсув (перезапись) всіх елементів масиву, щоб записати мінімальне значення в відповідну клітинку. Тобто алгоритм Сортування вибором не вимагає використання додаткової пам'яті. Перезапис значень відбувається відразу після знаходження мінімального значення в масиві.
Код програми дуже простий, і не вимагає якихось особливих описів:
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 не змінилась, значить з усього хвоста масиву, який обробляється, мінімального значення немає, і елемент “початку” залишається на своєму місці. Иначе – значення міняється місцями зі знайденим.
Хвіст оброблюваного масиву з кожним проходом циклів зменшується і коли досягне кінця масиву, він (массив) виявиться вже відсортованих. Робота алгоритму Сортування вибором припиниться.
Ось відмінне коротке відео з інформатики з розбором сортування вибором (вибір Сортування):
Прочитайте також наші наступні уроки присвячені алгоритмам сортування: пузырьковая сортировка і shyeikyernaya sortirovka массива.
Спасибо! Дуже зрозуміло і точно викладено алгоритм сортування.
Спасибо!