Алгоритмы сортировки: сравнение и анализ на си/c++

Сортировка данных — одна из самых важных задач в программировании. Различные алгоритмы сортировки отличаются по эффективности, сложности реализации и области применения.

В этой статье мы рассмотрим реализацию популярных алгоритмов сортировки на C++ (с использованием Qt для вывода результатов), а также подробно разберём понятие временной и пространственной сложности алгоритмов.

Сложность алгоритмов: обозначения и расшифровка

«O» (О-большое) — асимптотическая сложность

O(1)	Константная	Выполняется за фиксированное время, не зависит от размера входных данных. Пример: доступ к элементу массива по индексу.
O(log n)	Логарифмическая	Очень быстрая. Увеличение данных незначительно влияет на время. Пример: бинарный поиск.
O(n)	Линейная	Время работы пропорционально количеству данных. Пример: перебор всех элементов.
O(n log n)	Линейно-логарифмическая	Оптимальный уровень сложности для многих алгоритмов сортировки. Пример: быстрая сортировка (Quick Sort).
O(n²)	Квадратичная	Время увеличивается квадратично с ростом данных. Пример: пузырьковая сортировка, вложенные циклы.
O(2ⁿ)	Экспоненциальная	Очень медленно. При увеличении данных даже немного — время резко растёт. Пример: полный перебор подмножеств.

Вот график, показывающий, как растёт время выполнения различных алгоритмов в зависимости от размера входных данных n.

• Синие линии (O(1), O(log n), O(n)) — растут медленно, это эффективные алгоритмы.
• Жёлтые и красные линии (O(n²), O(2ⁿ)) — растут очень быстро, особенно O(2ⁿ) — она резко уходит вверх даже при малых n.

Основная идея:

Она описывается с помощью символа «O» (О-большое):

• O(1) — постоянное время: неважно, сколько данных, время выполнения всегда одинаково.
• O(n) — линейное время: если данных в 2 раза больше, время тоже в 2 раза больше.
• O(n²) — квадратичное время: если данных в 2 раза больше, время увеличится в 4 раза.
• O(log n) — логарифмическое время: даже если данные увеличатся в 1000 раз, время вырастет немного.

Виды сложности

1. Худший случай — максимальное время работы на самых «плохих» данных.
2. Средний случай — ожидаемое время на случайных данных.
3. Лучший случай — минимальное время (например, если массив уже отсортирован).

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

---

Простое объяснение:

Допустим, ты сортируешь стопку бумаг.

• Если у тебя 10 листов — ты уложился за минуту.
• А если 1 000 000 листов? За сколько?

Асимптотическая сложность помогает понять, во сколько раз увеличится время сортировки, если ты увеличишь количество листов.

---

Сортировка пузырьком (Bubble Sort)

Принцип работы:

• Последовательно сравниваются соседние элементы массива.
• Если порядок нарушен, элементы меняются местами.
• Процесс повторяется, пока массив не будет отсортирован.

Сложность:

Сценарий	Сложность	Комментарий
Худший случай	O(n²)	Все элементы в обратном порядке
Лучший случай (оптимизация)	O(n)	Массив уже отсортирован, нужен только один проход
Память	O(1)	Сортировка выполняется на месте, без доп. памяти

Плюсы:

• Простота реализации.
• Не требует дополнительной памяти.

Минусы:

• Медленный для больших массивов.

Когда использовать?

• Только для обучения или очень маленьких массивов.

Пример сортировки пузырьком (Bubble Sort)

#include <QDebug>

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // Оптимизация: если обменов не было, массив отсортирован
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, size);
    
    qDebug() << "Bubble Sort:";
    for (int i = 0; i < size; ++i) {
        qDebug() << arr[i];
    }
    
    return 0;
}

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

Принцип работы:

• На каждом шаге находится минимальный элемент в неотсортированной части массива.
• Этот элемент меняется местами с первым элементом неотсортированной части.

Сложность:

Сценарий	Сложность	Комментарий
Всегда	O(n²)	Независимо от того, отсортирован массив или нет
Память	O(1)	Сортировка выполняется на месте, не требует доп. памяти

Плюсы:

• Простота.
• Минимальное количество перестановок (всего n−1).

Минусы:

• Медленный, не адаптируется к частично отсортированным данным.

Когда использовать?

• Когда количество перезаписей критично (например, сортировка на SSD).

Пример сортировки выбором (Selection Sort)

void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        std::swap(arr[i], arr[minIndex]);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    selectionSort(arr, size);
    
    qDebug() << "Selection Sort:";
    for (int i = 0; i < size; ++i) {
        qDebug() << arr[i];
    }
    
    return 0;
}

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

Принцип работы:

• Массив разбивается на отсортированную и неотсортированную части.
• Каждый новый элемент вставляется в правильную позицию в отсортированной части.

Сложность:

Сценарий	Сложность	Комментарий
Худший случай	O(n²)	Если массив отсортирован в обратном порядке
Лучший случай	O(n)	Если массив почти отсортирован
Память	O(1)	Сортировка на месте, без использования доп. памяти

Плюсы:

• Эффективен для почти упорядоченных данных.
• Хорош для маленьких массивов.

Минусы:

• Медленный на больших массивах.

Когда использовать?

• В комбинации с другими алгоритмами (например, в Timsort).
• Для небольших или частично отсортированных данных.

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

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    insertionSort(arr, size);
    
    qDebug() << "Insertion Sort:";
    for (int i = 0; i < size; ++i) {
        qDebug() << arr[i];
    }
    
    return 0;
}

Быстрая сортировка (Quick Sort)

Принцип работы:

• Выбирается опорный элемент (pivot).
• Массив разбивается на две части: элементы меньше pivot и больше pivot.
• Рекурсивно сортируются обе части.

Сложность:

Сценарий	Сложность	Комментарий
Худший случай	O(n²)	Если pivot выбирается неудачно (например, всегда минимальный)
Средний случай	O(n log n)	На практике — очень быстрая сортировка
Память	O(log n)	Используется рекурсия, но без дополнительных структур данных

Плюсы:

• Один из самых быстрых на практике.
• Эффективно работает в среднем случае.

Минусы:

• Неустойчив (может менять порядок одинаковых элементов).
• Худший случай возможен при плохом выборе pivot.

Когда использовать?

• Для общего случая сортировки больших массивов.

Пример быстрой сортировка (Quick Sort)

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, size - 1);
    
    qDebug() << "Quick Sort:";
    for (int i = 0; i < size; ++i) {
        qDebug() << arr[i];
    }
    
    return 0;
}

Сортировка слиянием (Merge Sort)

Принцип работы:

• Массив рекурсивно разбивается на две части до отдельных элементов.
• Затем части сливаются в упорядоченном порядке.

Сложность:

Сценарий	Сложность	Комментарий
Всегда	O(n log n)	Независимо от порядка элементов
Память	O(n)	Требуется дополнительный массив для слияния

Плюсы:

• Стабильная сортировка — сохраняет порядок одинаковых элементов.
• Надёжная: всегда работает за O(n log n) — без худших случаев.

Минусы:

• Требует дополнительной памяти.

Когда использовать?

• Когда важна стабильность и гарантированное время работы.
• Для сортировки связанных списков.

Пример сортировки слиянием (Merge Sort)

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    mergeSort(arr, 0, size - 1);
    
    qDebug() << "Merge Sort:";
    for (int i = 0; i < size; ++i) {
        qDebug() << arr[i];
    }
    
    return 0;
}

Пирамидальная сортировка (Heap Sort)

Принцип работы:

• Построение max-heap (кучи) из массива.
• Последовательное извлечение максимального элемента и перестроение кучи.

Сложность:

Сценарий	Сложность	Комментарий
Всегда	O(n log n)	Нет худших случаев — работает стабильно
Память	O(1)	Не требует дополнительной памяти, всё в массиве

Плюсы:

• Надёжна и предсказуема: всегда O(n log n).
• Не использует дополнительную память — сортировка на месте.
• Лучше, чем Quick Sort, в гарантированном худшем случае.

Минусы:

• Нестабилен.
• Медленнее, чем Quick Sort на практике.

Когда использовать?

• Когда нужна сортировка на месте с гарантированной сложностью.

Пример пирамидальной сортировки (Heap Sort)

void heapify(int arr[], int size, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < size && arr[left] > arr[largest]) largest = left;
    if (right < size && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, size, largest);
    }
}

void heapSort(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; --i)
        heapify(arr, size, i);
    
    for (int i = size - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    heapSort(arr, size);
    
    qDebug() << "Heap Sort:";
    for (int i = 0; i < size; ++i) {
        qDebug() << arr[i];
    }
    
    return 0;
}

Сравнительная таблица

Алгоритм	Лучший случай	Средний случай	Худший случай	Память	Устойчивость
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Да
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	Нет
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Да
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	Нет
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Да
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	Нет

Вывод

Выбор алгоритма сортировки зависит от задачи:

• Для маленьких массивов подойдут Bubble Sort, Selection Sort или Insertion Sort.
• Для общего случая лучше использовать Quick Sort или Merge Sort.
• Если важна стабильность — Merge Sort.
• Если важна экономия памяти — Heap Sort или Quick Sort.

Каждый алгоритм имеет свои преимущества, и оптимальный выбор зависит от конкретных условий.