мета-данные страницы
  •  

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Следующая версия		Предыдущая версия
glossary:math:algorithms:quick_sort [2025/09/21 13:18] – создано radi0devglossary:math:algorithms:quick_sort [2025/11/09 12:07] (текущий) – внешнее изменение A User Not Logged in
Строка 29: Строка 29:
 #include <algorithm> // для std::copy, std::back_inserter #include <algorithm> // для std::copy, std::back_inserter
  
 +// Рекурсивная реализация quick sort, возвращающая новый вектор:
 +// - принимает const ссылку на входной вектор, чтобы не копировать сразу
 +// - возвращает отсортированный вектор
 std::vector<int> quick_sort(const std::vector<int>& arr) { std::vector<int> quick_sort(const std::vector<int>& arr) {
-  if (arr.size() <= 1) return arr; // базовый случай+  if (arr.size() <= 1) return arr; // базовый случай: пустой или единичный вектор уже отсортирован
      
 +  // Выбор опорного элемента — средний элемент вектора
   int pivot = arr[arr.size() / 2];   int pivot = arr[arr.size() / 2];
      
 +  // Разделяем элементы на три группы:
 +  // left  - элементы < pivot
 +  // middle - элементы == pivot (чтобы корректно обрабатывать дубликаты)
 +  // right - элементы > pivot
   std::vector<int> left, middle, right;   std::vector<int> left, middle, right;
-  left.reserve(arr.size());+  left.reserve(arr.size()); // резервируем память заранее, чтобы уменьшить число выделений
   middle.reserve(arr.size());   middle.reserve(arr.size());
   right.reserve(arr.size());   right.reserve(arr.size());
Строка 45: Строка 53:
   }   }
      
 +  // Рекурсивно сортируем левую и правую подпоследовательности
   std::vector<int> sorted_left = quick_sort(left);   std::vector<int> sorted_left = quick_sort(left);
   std::vector<int> sorted_right = quick_sort(right);   std::vector<int> sorted_right = quick_sort(right);
      
 +  // Объединяем результаты: отсортленная левая часть + середина + отсортированная правая часть
   std::vector<int> result;   std::vector<int> result;
-  result.reserve(sorted_left.size() + middle.size() + sorted_right.size());+  result.reserve(sorted_left.size() + middle.size() + sorted_right.size()); // резервируем итоговый размер
      
 +  // Копируем элементы в итоговый вектор
   std::copy(sorted_left.begin(), sorted_left.end(), std::back_inserter(result));   std::copy(sorted_left.begin(), sorted_left.end(), std::back_inserter(result));
   std::copy(middle.begin(), middle.end(), std::back_inserter(result));   std::copy(middle.begin(), middle.end(), std::back_inserter(result));
Строка 59: Строка 70:
  
 int main() { int main() {
-    std::vector<int> array = {10, 7, 8, 9, 1, 5}; +  // Пример использования: исходный массив 
-    std::vector<int> sorted_array = quick_sort(array); +  std::vector<int> array = {10, 7, 8, 9, 1, 5}; 
- +  // Получаем отсортированный массив (функция возвращает новый вектор) 
-    std::cout << "Отсортированный массив: "; +  std::vector<int> sorted_array = quick_sort(array); 
-    for (size_t i = 0; i < sorted_array.size(); ++i) { +   
-        if (i) std::cout << ", "; +  // Вывод результата в консоль 
-        std::cout << sorted_array[i]; +  std::cout << "Отсортированный массив: "; 
-    } +  for (size_t i = 0; i < sorted_array.size(); ++i) { 
-    std::cout << std::endl; +    if (i) std::cout << ", "; // выводим запятую перед элементом, начиная со второго 
-    return 0;+    std::cout << sorted_array[i]; 
 +  } 
 +  std::cout << std::endl; 
 +  return 0;
 } }
 </code> </code>