Сортировка методом Выбора (метод локального минимума)

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

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

1. Для нашей задачи, нужно перебрать все элементы массива, а на каждом шаге i, последовательность array[0]…array[i] будет отсортирована. Для этого создаем цикл с кол-вом итераций, равным кол-ву элементов массива:

for (i=0; i< size; i++)

2. На каждом шаге i, ищем минимальный элемент в неотсортированной части (array[i+1]…array[n-1]). Для этого создаем внутренний цикл с счетчиком-переменной j, меняющейся от начала неотсортированной части [i+1] до конца массива и проверяем в условии является ли меньше первого элемента неотсортированной части или нет и запоминаем наименьший элемент и его индекс в вспомогательных переменных:

for (j=i+1; j< size; j++)

if (array[j] < x) {

k=j;

x=array[j];

}

3. После того, как наименьший элемент будет найден, поменяем местами первый элемент неотсортированной части с наименьшим:

array[k]=array[i];

array[i]=x;

4. В случае, если наименьший элемент не будет найдет, в п.2 вставятся не то, что нужно, т.к. условие не выполнится и вспомогательным переменным ничего не присвоится. Чтобы этого избежать, перед внутренним циклом в п.2 присвоим вспомогательным переменным последний элемент отсортированной части:

k=i;

x=a[i];

Таким образом, блок-схема и весь алгоритм выглядит так:

Рис. 1.2. Блок-схема сортировки Выбором

long i, j, k, x;

for (i=0; i< size; i++){

k=i;

x=a[i];

for (j=i+1; j< size; j++)

if (array[j] < x) {

k=j;

x=array[j];

}

array[k]=array[i];

array[i]=x;

}

Для нахождения наименьшего элемента из n+1 рассматримаемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

n + (n-1) + (n-2) + (n-3) +... + 1 = 1/2 * (n²+n) = Theta(n²).

Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Алгоритм не использует дополнительной памяти: все операции происходят " на месте".

Поскольку равные элементы не меняются местами, алгоритм устойчивый.