Сортировка выбором С++ (видео)

Смысл Сортировки выбором (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;
}

#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):

Прочтите также наши следующие уроки посвященные алгоритмам сортировки: пузырьковая сортировка и шейкерная сортировка массива.

2 thoughts on “Сортировка выбором С++”

Tatiana Tverdokhlebova:
04.09.2015 в 20:48
Спасибо! Очень понятно и точно изложен алгоритм сортировки.
Ответить
Антон:
01.04.2021 в 10:26
Спасибо!
Ответить