Базовые алгоритмы сортировки

Введение

Дан массив

a_1, a_2, \ldots, a_n

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

Ниже приведены три простых классических алгоритма сортировки.

Пузырьковая сортировка

Пузырьковая сортировка выполняется за несколько проходов по массиву.

В каждом проходе мы сравниваем соседние элементы один за другим. Если они стоят в неправильном порядке, мы меняем их местами.

После каждого полного прохода как минимум один элемент перемещается на своё правильное место. Поэтому после $n-1$ проходов весь массив становится отсортированным.

Сортировка вставками

Сортировка вставками строит отсортированную часть массива слева направо.

На итерации $i$ мы предполагаем, что префикс

a[1 \ldots i]

уже отсортирован. Затем мы вставляем следующий элемент $a_{i+1}$ на его правильное место внутри этого отсортированного префикса.

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

Сортировка выбором также выполняется за $n-1$ итераций.

На итерации $i$ мы находим минимальный элемент в подмассиве

a[i \ldots n]

и меняем его местами с $a[i]$ .

После этого первые $i$ элементов находятся на своих правильных позициях.

for (int it = 0; it < n - 1; it++) {
    for (int i = 1; i <= n - 1; i++) {
        if (a[i] > a[i + 1]) {
            swap(a[i], a[i + 1]);
        }
    }
}

for (int i = 1; i <= n - 1; i++) {
    for (int j = i + 1; j > 1; j--) {
        if (a[j - 1] > a[j]) {
            swap(a[j - 1], a[j]);
        } else {
            break;
        }
    }
}

for (int i = 1; i <= n - 1; i++) {
    int min_index = i;
    for (int j = i + 1; j <= n; j++) {
        if (a[j] < a[min_index]) {
            min_index = j;
        }
    }
    swap(a[i], a[min_index]);
}