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

Вот основные алгоритмы сортировки сравнением с их характеристиками и реализациями на C++.

Квадратичные сортировки (O(n²))

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

   • Идея: Элемент вставляется в отсортированную часть массива.
   • Сложность: O(n²) в худшем/среднем, O(n) в лучшем (почти отсортированный массив).
   • Стабильная, in-place. Полезна для маленьких массивов (n ≤ 10).

     void insertionSort(std::vector<int>& arr) {
     for (size_t i = 1; i < arr.size(); ++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. Сортировка выбором (Selection Sort)

   • Идея: Находим минимальный элемент в неотсортированной части и меняем его с первым элементом этой части.
   • Сложность: Всегда O(n²). Нестабильная, in-place.

Сортировки за O(n log n)

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

   • Идея: Алгоритм «разделяй и властвуй». Выбирается опорный элемент (pivot), массив делится на две части: меньше опорного и больше. Рекурсивно сортируются части.
   • Сложность: O(n log n) в среднем, O(n²) в худшем (плохой выбор pivot). Нестабильная, in-place. Часто самый быстрый на практике.

     int partition(std::vector<int>& arr, int low, int high) {
     int pivot = arr[high];
     int i = low - 1;
     for (int j = low; j < high; ++j) {
         if (arr[j] <= pivot) std::swap(arr[++i], arr[j]);
     }
     std::swap(arr[i + 1], arr[high]);
     return i + 1;
     }
     void quickSort(std::vector<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);
     }
     }

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

   • Идея: Алгоритм «разделяй и властвуй». Массив рекурсивно делится пополам, сортируется каждая половина, затем отсортированные половины сливаются.
   • Сложность: Всегда O(n log n). Стабильная. Требует O(n) дополнительной памяти.

5. Пирамидальная сортировка (Heap Sort)

   • Идея: Строится max-heap из массива. Максимум (корень) меняется с последним элементом, куча уменьшается и перестраивается. Процесс повторяется.
   • Сложность: Всегда O(n log n). Нестабильная, in-place. Медленнее QuickSort в среднем, но имеет гарантированную сложность.

     void heapify(std::vector<int>& arr, int n, int i) {
     int largest = i, left = 2*i + 1, right = 2*i + 2;
     if (left < n && arr[left] > arr[largest]) largest = left;
     if (right < n && arr[right] > arr[largest]) largest = right;
     if (largest != i) {
         std::swap(arr[i], arr[largest]);
         heapify(arr, n, largest);
     }
     }
     void heapSort(std::vector<int>& arr) {
     int n = arr.size();
     for (int i = n/2 - 1; i >= 0; --i) heapify(arr, n, i); // Построение кучи
     for (int i = n-1; i > 0; --i) {
         std::swap(arr[0], arr[i]); // Извлечение максимума
         heapify(arr, i, 0); // Восстановление кучи
     }
     }

В C++ для сортировки обычно используют std::sort (гибрид QuickSort, HeapSort и InsertionSort, O(n log n)) и std::stable_sort (стабильная сортировка, часто MergeSort).