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

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

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

1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;

2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key;

3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key≠1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;

4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по n, так как элемент A[1] уже занимает свою позицию.

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

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

Рисунок 6.2 – Пример сортировки выбором

 

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

 

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() //главная функция

{

int n, A[1000];

cout<<"Количество элементов > "; cin>>n;

for (i=0; i<n; i++) //ввод массива

{

cout<<i+1<<" элемент > ";

cin>>A[i];

}

SelectionSort(A, n);

}

 

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

 

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

end.

 

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