Search code examples
c++algorithmsortingquicksort

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?

Solution

  • 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.