Алгоритм быстрой сортировки со схемой разбиения Hoare возвращает исходный несортированный список

Question

Я пытался реализовать алгоритм быстрой сортировки с помощью схемы разбиения Hoare, но когда я запускаю его в тестовом списке {412, 123, 57, 12, 1, 5}, а затем распечатываю, я получаю числа в исходном порядке.Может ли кто-нибудь помочь мне определить, что я делаю неправильно?Ниже моя реализация.

void Quicksort::sort(std::vector<int> &list)
{
   sort(list, 0, list.size() - 1);
}

void Quicksort::sort(std::vector<int> &list, int left, int right)
{
   if (left - right <= 1) return; // no need to partition a single element
   int pivot = left + (right - left) / 2; // <=> (left+right)/2, but avoids overflow
   int endIndex = partition(list, pivot, left, right); 
   sort(list, 0, endIndex - 1);
   sort(list, endIndex + 1, list.size() - 1);
}

int Quicksort::partition(std::vector<int> &list, int pivot, int left, int right)
{
   while (true)
   {
      while (list[left] < list[pivot])
         left++;
      while (list[right] > list[pivot])
         right--;
      if (left != right)
         std::swap(list[left], list[right]);
      else
         return left;
   }
}

Для вызова алгоритма быстрой сортировки в списке {412, 123, 57, 12, 1, 5} Я использую следующий код:

std::vector<int> numbers = {412, 123, 57, 12, 1, 5};
Quicksort::sort(numbers);
for (int i = 0; i < numbers.size(); i++)
   std::cout << numbers[i] << "\n";

Вывод на консоль

412
123
57
12
1
5

Редактировать

После исправления ошибки if (left - right <= 1), которая должна быть if (right - left <= 1), программа обнаружит ошибку Segmentation fault: 11.Это заставляет меня поверить, что я пытаюсь получить доступ к чему-то, что находится за пределами.

Answer 1

Разделенная часть алгоритма не реализована правильно.В частности, left может стать больше, чем right, и это

if (left != right)
     std::swap(list[left], list[right]);
//             ^^^^^^^^^^

Может получить доступ к вектору за пределами.

Посмотрите на следующий фрагмент:

int partition(std::vector<int> &list, int left, int right)
{
   // I'm calculating the pivot here, instead of passing it to the function
   int pivot = list[left + (right - left) / 2];
   while (true)
   {
      while (list[left] < pivot)
         left++;
      while (list[right] > pivot)
         right--;

      // Stop when the pivot is reached 
      if (left >= right)
         return right;

      // Otherwise move the elements to the correct side 
      std::swap(list[left], list[right]);
   }
}

void sort(std::vector<int> &list, int left, int right)
{
    // Execute only if there are enough elements
   if (left < right) 
   {
       int pivot = partition(list, left, right);

       // As NiVer noticed, you have to limit the range to [left, right]
       sort(list, left, pivot - 1); 
       sort(list, pivot + 1, right);
   }
}

Тестируемый ЗДЕСЬ .

Рассмотрим также реализацию этих функций в более общем виде с использованием итераторов.

Answer 2

Я считаю, что проблема (или, по крайней мере, одна проблема) кода заключается в строках:

sort(list, 0, endIndex - 1);
sort(list, endIndex + 1, list.size() - 1);

При этом учитывается всегда весь список, а не только часть , оставшаяся несортированной ,Вы должны использовать ограничивающие индексы left и right:

sort(list, left, endIndex - 1);
sort(list, endIndex + 1, right);