Problem with implementing QuickSort with C++

Question

So the answer turned out to be partially correct for this simple code. The result is "1 1 2 3 4 4 2 6 8 5 " I think the problem should be related to recursion and partitioning. Where did I do wrong??

#include <iostream>

using namespace std;


void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high){
    int i = low - 1;
    int pivot = num[high];
    for(int j = low; j <= high -1; j++){
        if(num[j] <= pivot){
            i++;
            swap(&num[i], &num[j]);
        }
        else{
            continue;
        }
    swap(&num[i+1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i+2, high);
    }
}

int main(){
    int test[] = {3,1,2,6,5,4,8,1,2,4};
    quick_sort(test, 0, sizeof(test)/sizeof(test[0])-1);
    for(int i = 0; i < sizeof(test)/sizeof(test[0]); ++i){
        cout << test[i] << endl;
    }
    return 0;

}

I don't understand. `low` starts at `0`, but `i` is `low - 1`. So on your first iteration, you have an index equal to `-1`? — KABoissonneault, Feb 11 '19 at 14:29
@KABoissonneault I almost made the same jump, but he does at least a i++ in once in the loop before using it :) and every where else i+1 or i+2 so it is ok.. as far as that is concerned. — Rob, Feb 11 '19 at 14:32
Why not step through the code in your favorite debugger, while watching the variables? — rustyx, Feb 11 '19 at 14:41
`using namespace std;` + `void swap(int* a, int* b)` isnt going to end well on the long run. Read this: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice — 463035818_is_not_an_ai, Feb 11 '19 at 14:55
See also: [C++ quicksort](https://stackoverflow.com/a/24650627/2610810) — Caleth, Feb 11 '19 at 14:55
In the case where the pivot is the smallest value, you fall off the beginning of the range recusing `quick_sort(num, low, i);` — Caleth, Feb 14 '19 at 17:24

Loc Tran · Accepted Answer · 2019-02-14T16:04:42.123

Your problem is the for loop. The i value should be updated after the for loop completed, then use i value for swap and other quick_sort calls. But your source code, i updated inside the for loop and used it for swap and other quick_sort calls. It is the problem. Here is my solution:

#include <iostream>

using namespace std;


void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high) {
    if (low >= high) return;
    int i = low - 1;
    int pivot = num[high];
    for (int j = low; j <= high - 1; j++) {
        if (num[j] <= pivot) {
            i++;
            swap(&num[i], &num[j]);
        }
        else {
            continue;
        }
    } // move to correct line
    swap(&num[i + 1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i + 2, high);
    // } this line should be moved to another line
}

int main() {
    int test[] = { 3,1,2,6,5,4,8,1,2,4 };
    quick_sort(test, 0, sizeof(test) / sizeof(test[0]) - 1);
    for (int i = 0; i < sizeof(test) / sizeof(test[0]); ++i) {
        cout << test[i] << endl;
    }
    return 0;

}

Sorry but I don't see any difference from your for loop and mine. — Yemin Yu, Feb 12 '19 at 03:09
You should probably edit this to not include `using namespace std;` and opt for the `std::` prefix instead. Especially for `swap`. — Rietty, Feb 14 '19 at 16:06

score 0 · Answer 2 · answered Feb 12 '19 at 17:52

Like @Loc Tran pointed out, your pivot swap and subsequent left and right quick sorts must be outside for loop. There is no need of else continue;. The purpose of the for loop is to find the position(i) for our pivot element such that all elements to the left are smaller than pivot and to the right are larger that pivot.

Once the position(i+1) is identified, put the pivot there by swapping and then proceed quick sort on the left and right sides of pivot.

Also you should proceed quick sort only when low < high.

#include <iostream>

using namespace std;


void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int num[], int low, int high){
    if(low >= high)
        return;
    int i = low - 1;
    int pivot = num[high];
    for(int j = low; j <= high -1; j++){
        if(num[j] <= pivot){
            i++;
            swap(&num[i], &num[j]);
        }
    }
    swap(&num[i+1], &num[high]);
    quick_sort(num, low, i);
    quick_sort(num, i+2, high);
}

int main(){
    int test[] = {3,1,2,6,5,4,8,1,2,4};
    quick_sort(test, 0, sizeof(test)/sizeof(test[0])-1);
    for(int i = 0; i < sizeof(test)/sizeof(test[0]); ++i){
        cout << test[i] << endl;
    }
    return 0;

}

Problem with implementing QuickSort with C++

2 Answers2