Это наиболее естественный алгоритм упорядочивания. При данной сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n - 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. (рис. 12.2)
Шаги алгоритма:
1. находим минимальное значение в текущей части массива;
2. производим обмен этого значения со значением на первой неотсортированной позиции;
3. далее сортируем хвост массива, исключив из рассмотрения уже отсортированные элементы.
Рис. 12.2. Демонстрация сортировки по неубыванию методом простого выбора
//Описание функции сортировки методом простого выбора
void SelectionSort (int k,int x[max]) {
int i,j,min,temp;
for (i=0;i<k-1;i++) {
//устанавливаем начальное значение минимального индекса
min=i;
//находим минимальный индекс элемента
for (j=i+1;j<k;j++){
if (x[j]<x[min])
min=j;
//меняем значения местами
}
temp=x[i];
x[i]=x[min];
x[min]=temp;
}
}
Как и в пузырьковой сортировке, внешний цикл выполняется n-1 раз, а внутренний – в среднем n/2 раз. Следовательно, сортировка методом простого выбора требует
сравнений. Таким образом, это алгоритм порядка n2, из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке простым выбором одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.
