C Academy · Урок

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

Разделяйте и властвуйте

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

Разделяй и властвуй

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

Среднее время работы составляет O(n log n).

Этап разделения

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

Схема разделения Ломуто

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

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
    return i + 1;
}

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

Рекурсивная сортировка

Быстрая сортировка вызывает разделение, а затем рекурсивно обрабатывает два подмассива по разные стороны от опорного элемента. Базовый случай — подмассив из 0 или 1 элемента.

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
    return i + 1;
}

void quicksort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}

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

Выбор хорошего опорного элемента

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

Медиана из трёх
Случайный опорный элемент

Медиана из трёх

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

#include <stdio.h>

int median_of_three(int a[], int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
    if (a[hi] < a[lo])  { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
    if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
    return mid;
}

int main(void) {
    int a[] = {7, 1, 5, 3, 9};
    int m = median_of_three(a, 0, 4);
    printf("median value = %d\n", a[m]);
    return 0;
}

Анализ худшего случая

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

Рандомизация делает худший случай крайне маловероятным.

Случайный опорный элемент

Обмен случайного элемента с элементом на позиции опорного перед разделением защищает от специально подобранных входных данных.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int a[] = {1, 2, 3, 4, 5};
    int lo = 0, hi = 4;
    srand(42);
    int r = lo + rand() % (hi - lo + 1);
    int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
    printf("chosen pivot = %d\n", a[hi]);
    return 0;
}

Сортировка на месте и нестабильность

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

Оптимизация хвостовой рекурсии

Рекурсивная обработка сначала меньшей половины и выполнение цикла для большей ограничивают глубину стека значением O(log n), предотвращая переполнение стека на больших массивах.

Сортировка строк

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

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
    if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}

int main(void) {
    int a[] = {42, -7, 0, 100, 13, 13};
    quicksort(a, 0, 5);
    for (int i = 0; i < 6; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

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

Проверьте своё понимание быстрой сортировки.

Итоги

Вы изучили быструю сортировку.

Разделите массив вокруг опорного элемента, затем рекурсивно обработайте обе части
Средняя сложность O(n log n), в худшем случае O(n²)
Медиана из трёх или случайный опорный элемент помогают избежать худшего случая
Сортировка выполняется на месте, но не является стабильной

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

Урок «Быстрая сортировка» бесплатный?

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

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

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

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

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

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

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

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

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

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

← Назад к C Academy