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

Сортировка выбором (Selection sort) – неустойчивый алгоритм сортировки, который можно описать следующим образом.

Пусть задан массив, содержащий n элементов. Для сортировки его элементов по возрастанию, этот алгоритм будет иметь следующую последовательность шагов:

1. Шаг инициализации. Минимальным элементом принимается текущий i -ый элемент массива;

2. Шаг итерации. Для всех последующих элементов j находится индекс минимального элемента массива. Если найденный индекс не совпадает с индексом текущего элемента, то текущий и минимальный элементы меняются местами.

3. Шаг выхода. Предыдущие шаги повторяются для всех элементов массива с номерами .

Например.

Пусть задан следующий массив:

Проход 1

Проход 2

Проход 3

Проход 4

Анализ вычислительной сложности данного алгоритма показывает, что для сортировки необходимо осуществить (n -1) проход на каждом i -ом проходе, где , необходимо провести (n - i -1) сравнений. Общее число сравнений . Таким образом, по числу сравнений алгоритм имеет порядок сложности .

Число перестановок элементов зависит от первоначального расположения элементов в массиве. В наилучшем случае, когда массив упорядочен по возрастанию, перестановок элементов не будет. В наихудшем случае, когда массив упорядочен по убыванию потребуется (n -1)-а перестановка. В среднем число перестановок будет .

Блок-схема алгоритма сортировки выбором имеет следующий вид:

Реализовать данный алгоритм на языке С++ можно следующим образом:

template < class T>

void SelectionSort(T *A, const int n)

{

T temp;

int imin;

for (int i = 0; i < n-1; i++)

{

imin=i;

for (int j=i+1; j<n; j++)

if (A[j]<A[imin])

imin=j;

if (imin!=i)

{

temp=A[i];

A[i]=A[imin];

A[imin]=temp;

}

}

}