Какие алгоритмы сортировки ты знаешь в контексте C++?

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

1. Стандартные алгоритмы сортировки в STL:

#include <algorithm>
#include <vector>

std::vector<int> data = {5, 2, 8, 1, 9};

// Быстрая сортировка (обычно hybrid алгоритм)
std::sort(data.begin(), data.end());

// Стабильная сортировка (сохраняет порядок равных элементов)
std::stable_sort(data.begin(), data.end());

// Частичная сортировка (первые n элементов)
std::partial_sort(data.begin(), data.begin() + 3, data.end());

// N-th element (разделение)
std::nth_element(data.begin(), data.begin() + 2, data.end());

2. Базовые алгоритмы, которые реализовывал:

Bubble Sort (O(n²)):

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

Quick Sort (O(n log n) в среднем):

template<typename T>
int partition(std::vector<T>& arr, int low, int high) {
    T 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;
}

template<typename T>
void quick_sort(std::vector<T>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

Merge Sort (O(n log n), стабильный):

template<typename T>
void merge(std::vector<T>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<T> 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++];
        } else {
            arr[k] = R[j++];
        }
        k++;
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

3. Специализированные сортировки для C++:

Heap Sort с использованием std::make_heap:

void heap_sort(std::vector<int>& arr) {
    // Преобразуем в max-heap
    std::make_heap(arr.begin(), arr.end());

    // Извлекаем максимальный элемент и перестраиваем кучу
    for (auto it = arr.end(); it != arr.begin(); --it) {
        std::pop_heap(arr.begin(), it);
    }
}

4. Критерии выбора алгоритма в C++ проектах:

5. Практический опыт оптимизации:

• Использование Insertion Sort для маленьких подмассивов в Quick Sort (как в std::sort)
• Introsort — гибрид Quick Sort, Heap Sort и Insertion Sort (используется в STL)
• Сортировка указателей вместо больших объектов

• Радикальная сортировка (Radix Sort) для целых чисел с известным диапазоном:

  void radix_sort(std::vector<int>& arr) {
  const int BASE = 10;
  int max_val = *std::max_element(arr.begin(), arr.end());
  
  for (int exp = 1; max_val / exp > 0; exp *= BASE) {
      std::vector<int> output(arr.size());
      std::array<int, BASE> count = {0};
  
      for (int num : arr) {
          count[(num / exp) % BASE]++;
      }
  
      for (int i = 1; i < BASE; i++) {
          count[i] += count[i - 1];
      }
  
      for (int i = arr.size() - 1; i >= 0; i--) {
          int digit = (arr[i] / exp) % BASE;
          output[count[digit] - 1] = arr[i];
          count[digit]--;
      }
  
      arr = std::move(output);
  }
  }

6. Особенности C++ для сортировки:

• Возможность передавать custom comparator:

  
  struct Person {
  std::string name;
  int age;
  };

std::vector people; // Сортировка по возрасту std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) { return a.age < b.age; });

*   Использование `std::ranges::sort` в C++20
*   Сортировка с move-семантикой для тяжелых объектов
*   Parallel sorting с execution policies в C++17