Сортировка выбором

Сортировка выбором – возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду.

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;
2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key;
3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key≠1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;
4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.

Рассмотрим работу алгоритма на примере конкретной последовательности целых чисел. Дан массив, состоящий из пяти целых чисел 9, 1, 4, 7, 5 (см. рис.). Требуется расположить его элементы по возрастанию, используя сортировку выбором. Начнем по порядку сравнивать элементы. Второй элемент меньше первого – запоминаем это (key=2).

Далее мы видим, что он также меньше и всех остальных, а так как key≠1, меняем местами первый и второй элементы. Продолжим упорядочивание оставшейся части, пытаясь найти замену элементу со значением 9. Теперь в key будет занесена 3-ка, поскольку элемент с номером 3 имеет наименьшее значение. Как видно, key≠2, следовательно, меняем местами 2-ой и 3-ий элементы. Продолжаем расставлять на места элементы, пока на очередном шаге размер поддмассива не станет равным 1-ому.

Код программы на C++:

#include "stdafx.h"
#include <iostream>
using namespace std;
int i, j;
void SelectionSort(int A[], int n) //сортировка выбором
{
int count, key;
for (i=0; i<n-1; i++)
{
count=A[i]; key=i;
for (j=i+1; j<n; j++)
if (A[j]<A[key]) key=j;
if (key!=i)
{
A[i]=A[key];
A[key]=count;
}
}
cout<<"Результирующий массив: ";
for (i=0; i<n; i++) cout<<A[i]<<" "; //вывод массива
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
int n, A[1000];
cout<<"Количество элементов > "; cin>>n;
for (i=0; i<n; i++) //ввод массива
{ cout<<i+1<<" элемент > "; cin>>A[i]; }
SelectionSort(A, n);
system("pause>>void");
}

Код программы на Pascal:

program SelectSort;
uses crt;
const max=1000;
type arr=array[1..max] of integer;
var i, j, n: integer;
A: arr;
procedure SelectionSort(A: arr; n: integer); {сортировка выбором}
var key, count: integer;
begin
for i:=1 to n do
begin
count:=A[i]; key:=i;
for j:=i+1 to n do
if (A[key]>A[j]) then key:=j;
if (key<>i) then
begin
A[i]:=A[key];
A[key]:=count;
end;
end;
write('Результирующий массив: ');
for i:=1 to n do write(A[i], ' '); {вывод массива}
end;
{основной блок программы}
begin
write('Количество элементов > '); read(n);
for i:=1 to n do {ввод массива}
begin
write(i,' элемент > '); read(A[i]);
end;
SelectionSort(A, n);
readkey;
end.

Сортировка выбором проста в реализации, и в некоторых ситуациях стоит предпочесть ее наиболее сложным и совершенным методам. Но в большинстве случаев данный алгоритм уступает в эффективности последним, так как в худшем, лучшем и среднем случае ей потребуется О(n²) времени.