C Academy · Урок

Сортировка пузырьком и вставками

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

«Сортировка пузырьком и вставками» — бесплатный урок C Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

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

Пузырьковая сортировка и сортировка вставками — два самых простых алгоритма сортировки сравнением. В худшем случае оба работают за O(n²), но их легко понять, и они полезны для небольших или почти отсортированных массивов.

Как работает пузырьковая сортировка

Пузырьковая сортировка многократно проходит по массиву, меняя местами соседние элементы, расположенные в неправильном порядке. После каждого полного прохода наибольший из оставшихся элементов всплывает на своё окончательное место в конце.

Обмен двух целых чисел

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

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

int main(void) {
    int x = 1, y = 2;
    swap(&x, &y);
    printf("%d %d\n", x, y);
    return 0;
}

Реализация пузырьковой сортировки

Используются вложенные циклы: внешний цикл считает проходы, а внутренний сравнивает соседние пары и меняет их местами. После прохода i последние i элементов отсортированы.

#include <stdio.h>

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    bubble_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Оптимизация с досрочным завершением

Если за полный проход не выполнено ни одного обмена, массив уже отсортирован и можно остановиться. Благодаря этому на уже отсортированных входных данных пузырьковая сортировка работает за O(n).

#include <stdio.h>

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
            }
        if (!swapped) break;
    }
}

int main(void) {
    int a[] = {1, 2, 3, 4, 5};
    bubble_sort(a, 5);
    printf("sorted with early exit\n");
    return 0;
}

Как работает сортировка вставками

Сортировка вставками формирует отсортированную область в начале массива. Для каждого нового элемента она сдвигает большие отсортированные элементы вправо и вставляет новый элемент на его место, подобно сортировке игральных карт в руке.

Реализация сортировки вставками

Возьмите элемент key = a[i], затем сдвиньте каждый элемент, больший него, в диапазоне a[0..i-1] на одну позицию вправо и вставьте key в образовавшийся промежуток.

#include <stdio.h>

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    insertion_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Сортировка вставками почти отсортированных данных

Сортировка вставками особенно эффективна, когда массив почти отсортирован: каждый элемент перемещается всего на несколько позиций, и время работы приближается к O(n). Поэтому её используют на завершающем этапе гибридных алгоритмов сортировки.

#include <stdio.h>

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
        a[j+1] = key;
    }
}

int main(void) {
    int a[] = {1, 2, 4, 3, 5}; /* one out of place */
    insertion_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Стабильность

Оба алгоритма являются стабильными: равные элементы сохраняют исходный взаимный порядок, поскольку обмен или сдвиг выполняется только при строгом сравнении «больше». Стабильность важна при сортировке записей по нескольким ключам.

Сравнение сложности

В среднем и в худшем случае оба алгоритма работают за O(n²), но на практике различаются:

Пузырьковая сортировка: много обменов, редко используется в настоящем коде
Сортировка вставками: меньше операций записи, отлично подходит для небольших или почти отсортированных массивов

С оптимизациями в лучшем случае оба алгоритма работают за O(n).

Подсчёт операций

Давайте подсчитаем количество сравнений, которые выполняет сортировка вставками на обратно отсортированном массиве — это худший случай.

#include <stdio.h>

int main(void) {
    int a[] = {5, 4, 3, 2, 1};
    int n = 5; long cmp = 0;
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
        a[j+1] = key;
    }
    printf("comparisons = %ld\n", cmp);
    return 0;
}

Быстрая проверка

Проверьте своё понимание простых алгоритмов сортировки.

Итоги

Вы изучили два простых алгоритма сортировки за O(n²).

Пузырьковая сортировка меняет соседние пары при каждом проходе
Сортировка вставками сдвигает элементы и вставляет новый элемент в начало отсортированной области
Оба алгоритма стабильны и после оптимизации работают за O(n) на отсортированных данных
Для небольших объёмов данных на практике лучше выбирать сортировку вставками

Часто задаваемые вопросы

Урок «Сортировка пузырьком и вставками» бесплатный?

Да — полный текст урока «Сортировка пузырьком и вставками» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Сортировка пузырьком и вставками»?

Простые алгоритмы сортировки Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Сортировка пузырьком и вставками»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к C Academy