Int i_min, i, j, r;

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

i_min = i;

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

if (a[i_min] > a[j]) i_min = j;

if (i_min!= i) { // Переставляем элементы

r = a[i_min]; a[i_min] = a[i]; a[i] = r;

}

}

}

Реже используются: 3) сортировка с помощью прямого (двоичного) включения; 4) шейкерная сортировка (модификация пузырьковой).

К улучшенным методам сортировки относятся следующие.

1. Метод Д. Шелла (1959), усовершенствование метода прямого включения.

2. Сортировка с помощью дерева, метод HeapSort, Д. Уильямсон (1964).

3. Сортировка с помощью разделения, метод QuickSort, Ч. Хоар (1962), улучшенная версия пузырьковой сортировки, являющийся на сегодняшний день самым эффективным методом.

Идея метода разделения QuickSort заключается в следующем. Выбирается значение ключа среднего m -го элемента x = a [ m ]. key. Массив просматривается слева направо до тех пор, пока не будет обнаружен элемент a [ i ]. key > x. Затем массив просматривается справа налево, пока не будет обнаружен элемент a [ j ]. key < x. Элементы a [ i ] и a [ j ] меняются местами. Процесс просмотра и обмена продолжается до тех пор, пока i не станет больше j. В результате массив оказывается разбитым на левую часть a [ L ],0 £ L £ j с ключами меньше (или равными) x и правую a [ R ], i £ R < n с ключами больше (или равными) x.

Алгоритм такого разделения очень прост и эффективен:

i = 0; j = n – 1; x = a[(L + R)/2].key;

while (i <= j) {

while (a[i].key < x) i++;

while (a[j].key > x) j--;

if (i <= j) {

r = a[i]; // Переставляем элементы

a[i] = a[j];

a[j] = r;

i++; j--;

}

}

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

Рекурсивная функция сортировки элементов целочисленного динамического массива а размера n может иметь следующий вид (begin – первый элемент массива, end – последний элемент массива):

void Quick_Sort(int *a, int begin, int end)

{

int left, right, x;

left = begin;

right = end;

x = a[(left+right)/2];

do {

while(a[left] <x) left++;

while(x < a[right]) right--;

if(left <= right){

x = a[left];

a[left] = a[right];

a[right] = x;

left++;

right--;

}

} while(left<=right);

if(begin < right) Quick_Sort(a, begin, right);

if(left < end) Quick_Sort(a, left, end);

}

Обращение к этой функции Quick_Sort(a, 0, n-1);

Сравнение методов сортировок показывает, что при n > 100 наихудшим является метод пузырька, метод QuickSort в 2-3 раза лучше, чем HeapSort, и в 3-7 раз, чем метод Шелла.