Quick Sort Error, Possibly an off by 1 C++

Question

Trying to write a quick sort and have spent awhile debugging. The problem seems to be in the second recursive call, but I can't figure out where I'm off. Any pointer would be awesome. Thanks.

void quickSort(vector<int> &list, int left, int right){

    int pivot = left;
    int temp = right;

    if(left >= right - 1)
        return;

    while (left != right) {
        if (pivot == left){
            if (list[pivot] > list[right]) {
                //-------------------------
                int tempList = list[right];
                list[right] = list[pivot];   // Swap for now
                list[pivot] = tempList;
                //-------------------------
                pivot = right;
                left++;
            }else{
                right--;
            }

        }else{
            if (list[pivot] < list[left]) {
                //-------------------------
                int tempList = list[left];
                list[left] = list[pivot];   // Swap for now
                list[pivot] = tempList;
                //-------------------------
                pivot = left;
                right--;
            }else{
                left++;
            }
        }
    }
    quickSort(list, 0, right-1);
    quickSort(list, right + 1, temp);
}

This is how I'm making the data set right now:

srand(time(0));
vector<int> list;
vector<int> sortedList;
int i;
for (i=0;i<10;i++) list.push_back(rand() %100);

I got a data set of 38 65 26 22 86 64 13 28 57 18

and got an output of 13 18 22 26 28 38 57 64 86 65

It's usually an element in the last half, but it's also not every time. Maybe 1 in 4 times.

Answer 1

Since you are accessing elements at location right and left I assume that the initial call is as follows:

quickSort(list, 0, list.size()-1);

If the list is initially initialized as vector<int>{ 2, 1 } the first call will evalute to

quickSort(list, 0, 1);

With left=0 and right=1 the first if-statement will evaluate to

    if(0 >= 1-1)
        return;

and the function will return without swapping the two elements, even if the list is clearly unsorted.