Quicksort infinite loop if there are repeating values

Question

I have a quicksort program that works great until I try to sort an array that has a repeating number. The program gets stuck in an infinite loop. I believe this is happening in the While(lower < upper) block of code.

void quickSort(int array[], int size){
  if(size < 2) return;

  int pivot, lower, upper, temp;

  //Set the indeces for the first and last elements                                 
  lower = 0;
  upper = size - 1;

  //Select pivot element randomly                                                   
  pivot = array[rand() % (size)];                                                                                                     

  while(lower < upper){
    //Lower must be a number < than pivot and upper a number >= pivot               
    while(array[lower] < pivot){
      lower++;
    }
    while(array[upper] > pivot){
      upper--;
    }

    //Swap upper and lower                                                          
    temp = array[lower];
    array[lower] = array[upper];
    array[upper] = temp;
  }

  //Repeat the past actions on the two partitions of the array recursively          
  quickSort(array, lower);
  quickSort(&array[lower+1], size-lower-1);
}

You are right. Taking quick view on your code it may happen that neither lower is increased nor upper decremented, which results in inf. loop. (finding such a case is easy i.e. all numbers to sort all the same) — gregory561, Dec 03 '13 at 15:56
What happens when there are multiple instances of the pivot value? The two innermost `while` loops will never cause `lower` and `upper` to meet. One should be `< pivot` and the other `>= pivot`. — Joe Z, Dec 03 '13 at 15:58
Your comment about the relations between upper/lower and the pivot doesn't agree with the code, so one of them is probably wrong. — molbdnilo, Dec 03 '13 at 16:00
@JoeZ I tried that but I end up getting a segmentation fault. — Kalmar, Dec 03 '13 at 16:05
You may also need to test upper >= lower in that while loop, then. — Joe Z, Dec 03 '13 at 16:28
What's the smallest array you found that hits this bug? What happened when you stepped through sorting this array in the debugger? What _should_ have happened? — Useless, Dec 03 '13 at 16:38

Abhishek Bansal · Accepted Answer · 2013-12-03T16:49:59.690

EDIT: Code added.

From Wikipedia, the pseudo-code for in-place quicksort is as follows:
(Not saying that they should be trusted blindly)

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

So you see it is quite similar to your algorithm, with minor modifications.

while(lower <= upper){

Also you need to swap only if lower <= upper and then update the indices.

And your code differs in the recursive calls:

quicksort(array from first index to right) {array[0] to array[upper]}
quicksort(array from left to last index) {array[lower] to array[size-1]}

This is because now that it has exited the while loop, upper is less than lower.

Full working code:

#include <iostream>
#include <cstdlib>
using namespace std;

void quickSort(int array[], int size){
  if(size < 2) return;

  int pivot, lower, upper, temp;

  //Set the indeces for the first and last elements                                 
  lower = 0;
  upper = size - 1;

  //Select pivot element randomly                                                   
  pivot = array[rand() % (size)];                                                                                                     

  while(lower <= upper){
    //Lower must be a number < than pivot and upper a number >= pivot               
    while(array[lower] < pivot){
      lower++;
    }
    while(array[upper] > pivot){
      upper--;
    }

    //Swap upper and lower                                                          
    if ( lower <= upper ) {
        temp = array[lower];
        array[lower] = array[upper];
        array[upper] = temp;
        lower++;
        upper--;
    }
  }

  //Repeat the past actions on the two partitions of the array recursively          
  quickSort(array, upper+1);
  quickSort(&array[lower], size-lower);
}

int main() {
    // your code goes here
    int myArray[] = { 10, 9, 8, 7, 7, 7, 7, 3, 2, 1};
    quickSort( myArray, 10 );
    for ( int i = 0; i < 10; i++ )
        cout << myArray[i] << " ";
    return 0;
}

Output:

1 2 3 7 7 7 7 8 9 10

Quicksort infinite loop if there are repeating values

1 Answers1

Linked