QuickSort Implementation Code in C++

13 Comments on “QuickSort Implementation Code in C++”

1. This quicksort algorithm will not work for an array with all the same numbers – an infinite loop ocurrs. To remove the infinte loop, change ‘if (left < right)’ to ‘if (left < right && a[left] != a[right])’.

2. Does that correction go into quicksort() or partition()?

3. Hi Brook – it goes in the partition function – I’ve now fixed the Quick Sort code in the post.

   Here’s the test code for all the values being the same.

   int numbers5[] = {7, 7, 7, 7, 7};
   quicksort(numbers5, 0, 4);
   printArray(numbers5, 5);

   And in case anyone is having trouble setting this up in Visual Studio here are the includes you need:

   #include "stdafx.h"
   #include 
   using namespace std;

4. Doesn’T work because, I don’t have anything like a swap function? Is it in some of the standard libraries that cygwin is equipped with?

5. Hi keltik, the code hasn’t been tested on cygwin – I’m not sure if cygwin has a suitable swap function built in, but it should only take a few lines of code to write your own version. You just need to swap the numbers at the memory addresses passed in to the function.

6. Won’t work on the following input:
   {14, 19, 11, 20, 19, 16, 12, 19, 20, 21}

   Returns:
   11 12 14 16 19 19 20 19 20 21

   which is not sorted. For people who still need swap function – I wrote it:

   void swap(int & a, int & b)
   {
   int c = a;
   a = b;
   b = c;
   }

7. Try this site for a java algorithm similar to your c++ algorithm but which may work in all circumstances.
   http://www.algolist.net/Algorithms/Sorting/Quicksort

8. int arr[] = { 3,5,8,2,5,7,3,1,7,3};

   try this case, code is wrong.

9. if (left < right && a[left] != a[right])
   {
   swap(a[left], a[right]);
   }
   else
   {
   return right;
   }

   should be

   if (left < right)
   {
   if(a[left] != a[right])
   swap(a[left], a[right]);
   }
   else
   {
   return right;
   }

   or else we are not returning the pivot at correct location.

10. One more thing, if correct it in the way above

    while (a[left] pivot) right–;

    should be

    while (a[left] = pivot) right–;

    suppose a[left]==a[right]==pivot
    infinite loop

    regards.

11. won’t work for {3,6,8,6}
    fix

    void quickSort(int arr[], int left, int right)
    {
    if (left >= right) return;
    int l = left, r = right;
    int pivot = arr[(left + right)>>1];

    while (l <= r) {
    while (arr[l] pivot) r–;
    if (l <= r) {
    int temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
    l++;
    r–;
    }
    }
    quickSort(arr, left, r);
    quickSort(arr, l, right);
    }

12. {5,6,5} not working if pivot index =0

13. int part(int a[], int lo, int hi)
    {
    int p = a[lo]; //pivot fixed
    int i = lo;
    int j = hi;

    if ((hi – lo) <= 0) return lo;

    while (i<j)
    {
    while (a[i]<p && ij)
    {
    //p is the biggest
    –i;
    swap(a[lo], a[i]);
    –i;
    return i;
    }
    if (i == j)
    {
    return i;
    }

    while (a[j] > p && j >= i) –j;

    if (j <= i)
    {
    //p is the smallest
    return i;
    }

    if (i= p && a[j] = a[j] is always true
    if (a[j] == p)
    {
    if (a[i] == p)
    {
    ++i;
    }
    else
    {
    //a[i] > p is true
    swap(a[i], a[j]);
    –j;
    }
    }
    else // a[j] =p && a[j] p && a[j] < p
    swap(a[i], a[j]);
    ++i;
    –j;

    }
    }

    if (i < j) continue;
    else if (i == j)
    {
    if (a[i] p ) { swap(a[i], a[i + 1]); return i; }
    }
    }//if (i<j)
    }//while (i<j)

    return i;
    }

    void mysort(int a[], int low, int hi)
    {
    int x;
    if (low<hi)
    {
    x = part(a, low, hi);
    if (lowx)
    mysort(a, x+1, hi);
    }
    }