CODEWITHSUNDEEP
c++algorithmsortingquicksort
haz
haz

Reputation: 2288

C++ QuickSort implementation that sorts everything but a single element

This is my first time writing C++. I am trying to implement QuickSort referencing the MIT open course ware slides (Slides 4 and 17 specifically).

However, there is a bug:

input:  6 10 13 5 8 3 2 11 
output: 2 5 3 6 8 11 10 13

I'm not sure why the 5 is out of place. My code seems to mirror the slides perfectly.

#include <utility>

using namespace std;

template <typename T>
void print_array(T &arr) {
    for (int i : arr) {
        cout << i << " ";
    }
    cout << endl;
}

int partition(int* a, int p, int q) {
    int x = a[p];
    int i = p;
    for (int j = p+1; j < q; j++) {
        if (a[j] <= x) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[p], a[i]);
    return i;
}

void quicksort(int* a, int p, int r) {
    if (p < r) {
        int q = partition(a, p, r);
        quicksort(a, p, q-1);
        quicksort(a, q+1, r);
    }
}

int main() {
    int keys[8] = {6, 10, 13, 5, 8, 3, 2, 11};
    print_array(keys);
    quicksort(keys, 0, 8);
    print_array(keys);
    return 0;
}

Upvotes: 0

Views: 50

Answers (1)

user1196549
user1196549

Reputation:

The slide says for j ← p + 1 to q, which you turned to for (int j = p+1; j < q; j++). This is an off-by-one error.

Upvotes: 1

Related Questions