Простые сортировки

Три классических алгоритма с квадратичной сложностью. Полезны для малых данных и как базис для понимания более сложных методов.

Пузырьковая сортировка (Bubble Sort)

На каждом проходе «всплывает» наибольший элемент. O(n²) во всех случаях.

func bubbleSort(a []int) {
    n := len(a)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
            }
        }
    }
}

Сортировка выбором (Selection Sort)

На каждом шаге находит минимум в неотсортированной части и ставит его на место. O(n²), минимум обменов.

func selectionSort(a []int) {
    n := len(a)
    for i := 0; i < n-1; i++ {
        min := i
        for j := i + 1; j < n; j++ {
            if a[j] < a[min] { min = j }
        }
        a[i], a[min] = a[min], a[i]
    }
}

Сортировка вставками (Insertion Sort)

Строит отсортированную последовательность, вставляя элементы по одному. O(n²) в худшем, O(n) на почти отсортированных данных.

func insertionSort(a []int) {
    for i := 1; i < len(a); i++ {
        key := a[i]
        j := i - 1
        for j >= 0 && a[j] > key {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = key
    }
}

Сравнение

Алгоритм	Лучший	Средний	Худший	Память	Стабильная
Bubble	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	✓
Selection	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	✗
Insertion	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	✓

Для n < 20–30 вставками быстрее быстрых алгоритмов — нет накладных расходов рекурсии.

Упражнения

№	Задание	Сложность
1	Упражнение 1	easy
2	Упражнение 2	easy
3	Упражнение 3	medium
4	Упражнение 4	medium