C++ - Implementing quicksort using unsigned integers only?

Question

C++ - Implementing quicksort using unsigned integers only?

I have

std::vector<unsigned int> numbers;

thats filled with numbers and needs to be quickSorted without using int index - only unsigned int is allowed as vector index.

All the quickSort examples that I've seen break when I convert all "int" to "unsigned int" because of index may be -1 in some cases (due to j--).

edit: Here is one example

void quickSort(std::vector<unsigned int> &numbers, unsigned int left, unsigned int right) {
        unsigned int i = left, j = right;
        unsigned int tmp;
        unsigned int pivot = numbers.size()/2;

        /* partition */
        while (i <= j) {
              while (numbers[i] < pivot)
                    i++;
              while (numbers[j] > pivot)
                    j--;
              if (i <= j) {
                    tmp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = tmp;
                    i++;
                    j--;
              }
        };

        /* recursion */
        if (left < j)
              quickSort(numbers, left, j);
        if (i < right)
              quickSort(numbers, i, right);
  }

Modified version of: http://diogopinho.hubpages.com/hub/easy-quicksort-with-examples

Example above Segfaults because if j is unsigned int and becomes 0, j-- becomes a huge number (0xffffffff) and (i<=j) is always true. Does anyone know how to implement quickSort using unsigned int index only?

c++

algorithm

sorting

quicksort

asked on Stack Overflow Jan 28, 2014 by

user3245357 • edited Jul 14, 2019 by

Mahouk

2 Answers

If you look at the page you linked to containing the description of the pivot, it is incorrectly implemented. That can cause the pivot not to be found and j becoming less than 0. If the pivot is correctly chosen as a number which is included in the range, I think this algorithm will work too with unsigned integers.

answered on Stack Overflow Jan 28, 2014 by

wimh • edited Jan 28, 2014 by

wimh

This post is very old, but in case someone is still in the need, he can find an implementation which can tolerate unsigned int index here

int partition(int *a,int start,int end)
{
    int pivot=a[end];
    //P-index indicates the pivot value index

    int P_index=start;
    int i,t; //t is temporary variable

    //Here we will check if array value is 
    //less than pivot
    //then we will place it at left side
    //by swapping 

    for(i=start;i<end;i++)
    {
        if(a[i]<=pivot)
        {
            t=a[i];
            a[i]=a[P_index];
            a[P_index]=t;
            P_index++;
        }
     }
     //Now exchanging value of
     //pivot and P-index
      t=a[end];
      a[end]=a[P_index];
      a[P_index]=t;

     //at last returning the pivot value index
     return P_index;
 }
 void Quicksort(int *a,int start,int end)
 {
    if(start<end)
    {
         int P_index=partition(a,start,end);
             Quicksort(a,start,P_index-1);
             Quicksort(a,P_index+1,end);
    }
}

answered on Stack Overflow Jul 14, 2019 by

Mahouk • edited Jul 15, 2019 by

Mahouk

User contributions licensed under CC BY-SA 3.0