CODEWITHSUNDEEP
c++algorithmsortingquicksort
mooncow
mooncow

Reputation: 413

Quicksort algorithm with Hoare's Partitioning Scheme returns original unsorted list

I have tried to implement the Quicksort algorithm with Hoare's Partitioning Scheme, but when I run it on a test list {412, 123, 57, 12, 1, 5} and then print it out, I get the numbers in original order. Can someone help me spot what I am doing wrong? Below is my implementation.

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;
   }
}

To call the Quicksort algorithm on the list {412, 123, 57, 12, 1, 5} I use the following code:

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";

The console output is

412
123
57
12
1
5

Edit

After having fixed the bug if (left - right <= 1) which should be if (right - left <= 1), the program encounters the error Segmentation fault: 11. This leads me to believe that I am trying to access something that is out-of-bounds.

Upvotes: 1

Views: 594

Answers (2)

Bob__
Bob__

Reputation: 12799

The partition part of the algorithm isn't implemented in the correct way. In particular, left may become greater than right and this

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

Could access the vector out of bounds.

Look at the following snippet:

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);
   }
}

Testable HERE.

Consider also implementing those functions in a more general way, using iterators.

Upvotes: 4

NiVeR
NiVeR

Reputation: 9806

I believe the problem (or at least one problem) of the code are the lines:

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

This considers always the whole list, and not only the remaining unsorted part. You should be using the restricting indexes left and right:

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

Upvotes: 2

Related Questions