CodeUtility
Кодить проще - жить легче!
Алгоритмы C/C++

Быстрая сортировка (quick sort) в C и C++

В этом уроке вы реализуете быструю сортировку, разбивая массив относительно опорного элемента.

Введение

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

Главное

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

Визуализация: Быстрая сортировка (quick sort) в C и C++

O(n log n)

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

Примеры кода на C и C++

C
Запустить →
main.c
#include <stdio.h>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}
Результат выполнения
3 4 5 7 9 10
C++
Запустить →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Результат выполнения
3 4 5 7 9 10

Сравнение C и C++

Функция partition на C выбирает опорным последний элемент и с помощью переменной boundary отмечает границу области меньших элементов. В конце опорный элемент меняется местами с элементом на позиции boundary. Версия на C++ выражает разбиение короче через std::partition. Средняя сложность O(n log n), но неудачный выбор опорного элемента может поднять её до O(n²).

C

Циклы, указатели, длины и временные буферы пишутся явно.

C++

Итераторы и стандартные алгоритмы отделяют обработку от способа хранения данных.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

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

Попрактикуйтесь на задаче

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

Все задачи