Что такое алгоритмы сортировки и какие вы знаете?cplus-52

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

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

1. Простые сортировки в худшем случае)

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

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

Особенности:

  • Простая реализация
  • Худший случай O(n²)
  • Лучший случай O(n) для почти отсортированных данных

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

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; 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;
    }
}

Применение:

  • Маленькие массивы
  • Почти отсортированные данные

2. Эффективные сортировки в среднем)

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high-1; 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);
    }
}

Особенности:

  • В среднем O(n log n)
  • Худший случай O(n²) при неудачном выборе опорного элемента
  • Использует подход "разделяй и властвуй"

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

void merge(int arr[], int l, int m, int r) {
    // Реализация слияния двух подмассивов
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

Преимущества:

  • Всегда O(n log n)
  • Устойчивая сортировка
  • Хорошо параллелится

3. Специальные сортировки

Сортировка подсчётом (Counting Sort)

void countingSort(int arr[], int n, int range) {
    std::vector<int> count(range+1, 0);
    std::vector<int> output(n);
    
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
    
    for (int i = 1; i <= range; i++)
        count[i] += count[i-1];
    
    for (int i = n-1; i >= 0; i--) {
        output[count[arr[i]]-1] = arr[i];
        count[arr[i]]--;
    }
    
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

Условия применения:

  • Диапазон значений известен и невелик
  • O(n + k), где k — диапазон значений

Поразрядная сортировка (Radix Sort) Принцип работы:

  • Сортировка по отдельным цифрам/битам
  • Использует устойчивую сортировку как подпрограмму

Сравнение алгоритмов

АлгоритмЛучшийСреднийХудшийПамятьУстойчивость
ПузырьковаяO(n)O(n²)O(n²)O(1)Да
ВставкамиO(n)O(n²)O(n²)O(1)Да
БыстраяO(n log n)O(n log n)O(n²)O(log n)Нет*
СлияниемO(n log n)O(n log n)O(n log n)O(n)Да
ПодсчётомO(n + k)O(n + k)O(n + k)O(n + k)Да

  • Можно сделать устойчивой с дополнительной памятью

Стандартная библиотека C++

std::sort (обычно гибрид QuickSort + HeapSort)

#include <algorithm>
std::vector<int> vec = {4, 2, 5, 1, 3};
std::sort(vec.begin(), vec.end());

std::stable_sort (устойчивая сортировка)

struct Item { int value; int index; };
bool compareByValue(const Item& a, const Item& b) {
    return a.value < b.value;
}
std::stable_sort(items.begin(), items.end(), compareByValue);

Выбор алгоритма сортировки

  1. Маленькие массивы (<50 элементов): Insertion Sort
  2. Общий случай: std::sort (QuickSort вариант)
  3. Нужна устойчивость: std::stable_sort (MergeSort)
  4. Ограниченный диапазон значений: Counting Sort
  5. Очень большие данные: External Merge Sort

Резюмируем: выбор алгоритма сортировки зависит от размера данных, особенностей входных данных и требований к стабильности и памяти. В большинстве случаев в C++ следует использовать std::sort, но понимание работы различных алгоритмов важно для специализированных задач.

Вопросы

Собеседования