QuickSort работает с небольшими векторами, но не с большими

Question

Я пытался написать реализацию QuickSort, но в ней есть какая-то ошибка, которую я не могу определить. Приведенный ниже код хорошо работает с вектором небольшого размера, например 100, но когда я пытаюсь предоставить 10000 номеров из файла, программа не останавливается. Любая помощь будет великолепна.

int Partition(vector<int> &nums, int low, int high, unsigned long &numIterations) {
  int paritionIndex = low;
  int paritionElement = nums.at(paritionIndex);
  int potentialPivotIndex = low + 1;
  for (int i = low + 1; i < high; ++i) {
    if (paritionElement > nums.at(i)) {
      std::swap(nums.at(potentialPivotIndex), nums.at(i));
      ++potentialPivotIndex;
    }
  }
  std::swap(nums.at(potentialPivotIndex - 1), nums.at(paritionIndex));
  //++numIterations;
  return potentialPivotIndex - 1;
}

void QuickSort(vector<int> &nums, int low, int high, unsigned long &numIterations) {
  int p;
  if ((high - low) > 0) {
    p = Partition(nums, low, high, numIterations);
    QuickSort(nums, 1, p - 1, numIterations);
    QuickSort(nums, p + 1, high, numIterations);
  }
}

Answer 1

После долгих отладок я обнаружил две проблемы с моим исходным кодом.

1. В функции QuickSort я должен передать функции переменную low, но дал ее постоянное значение 1.
2. Я изменил for loop функции Partition на диапазон high], а не high), а основная функция называется функцией QuickSort с size - 1

Внесенные выше поправки исправили код, и я смог отсортировать векторы.

Answer 2

Ваша функция разбиения неверна. даже вывод, который он генерирует для входов меньшего размера, не является правильным. Я изменил его на основе кода, представленного здесь следующим образом:

int Partition(vector<int> &nums, int low, int high, unsigned long &numIterations) {

    int pivot = nums.at(high);    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (nums.at(j) <= pivot)
        {
            i++;    // increment index of smaller element
            swap(nums.at(i), nums.at(j));
        }
    }
    swap(nums.at(i + 1), nums.at(high));
    return (i + 1);
}