Алгоритмы C/C++

Быстрая сортировка

Pivot ставится на окончательное место, затем сортируются две части.

Что такое Быстрая сортировка?

Pivot ставится на окончательное место, затем сортируются две части.

Разделяйте значения вокруг pivot.

Важные моменты

Проверяйте пустые, одиночные, повторяющиеся и отсортированные данные.
Отделяйте корректность от оптимизации.
В production предпочитайте стандартную библиотеку.

Визуализация: Быстрая сортировка

O(n log n)

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

Примеры кода на 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++

В среднем O(n log n), при плохом pivot O(n²). C++ выражает разделение через std::partition.

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

C++

Итераторы и алгоритмы отделяют операцию от хранения.

Практические задания

Запустите обе версии и изменяйте их, сравнивая гарантии языков.

Проследите каждое сравнение.
Проверьте дубликаты и крайние значения.
Сравните со стандартной библиотекой.