CODEWITHSUNDEEP
c++algorithmsortingg++quicksort
Max Cruer
Max Cruer

Reputation: 110

Issue with custom C++ QuickSort

I am implementing the Quicksort algowithm myself in C++. But I have problems: the result isn't sorted!

Here are my files: Main file: quicksort.cpp:

#include <iostream>
#include <ctime>

#include "quicksort.h"
#include "utils.h"

using namespace std;

int main() {
    int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    print_array(arr);
    cout << endl;

    QuickSort<int, 10>::sort(arr);

    print_array(arr);
    cout << endl;

    return 0;
}

utils.h:

#ifndef UTILS_H
#define UTILS_H

#include <iostream>
#include <openssl/rand.h>
#include <algorithm>

using namespace std;

template<typename T, size_t N>
void print_array(T (&a)[N]) {
    cout << "{";
    for(auto i: a) { cout << i << ","; }
    cout << "}";
}

template<typename T, size_t N>
void shuffle_array(T (&a)[N]) {
    srand(unsigned(time(0)));
    random_shuffle(&a[0], &a[10], [](int i)-> int {
        unsigned char bytes[i];
        RAND_bytes(bytes, sizeof(bytes));
        return int(bytes[0] % i);
    });
}

#endif /* UTILS_H */

quicksort.h:

#ifndef QUICKSORT_H
#define QUICKSORT_H

#include <iostream>

#include "utils.h"

template<typename T, size_t N>
class QuickSort {
private:
    static bool less(T a, T b) {
        return a < b;
    }

private:
    static void exch(T (&a)[N], int i, int j) {
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

private:
    static int partition(T (&a)[N], int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        
        while(true) {
            while(less(a[++i], a[lo])) {
                if(i == hi) { break; }
            }

            while(less(a[lo], a[--j])) {
                if(j == lo) { break; }
            }

            if(i >= j) { break; }
            exch(a, i, j);
        }

        exch(a, lo, hi);
        return j;
    }

public:
    static void sort(T (&a)[N]) {
        shuffle_array(a);
        print_array(a);
        cout << endl;
        sort(a, 0, int(N - 1));
    }

private:
    static void sort(T (&a)[N], int lo, int hi) {
        if(hi <= lo) { return; }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
};

#endif /* QUICKSORT_H */

Am I missing something? I am compiling this on Linux with:

$ g++ -pipe -time -o quicksort.exe quicksort.cpp -lssl -lcrypto

Please help, I am new in C++.

Upvotes: 0

Views: 70

Answers (1)

Benny K
Benny K

Reputation: 990

First, the line exch(a, lo, hi); should be exch(a, lo, j);. It appears to solve your problem: https://godbolt.org/z/ehh31G

Second - if you're learning c++, use c++ features. That is, use the standard library. Use std::array<T, N> indtead of T[N]. Use iterators instead of ints for lo, hi, i, j. exch can be replaced with std::swap. less can be replaced with std::less.

Third - DO NOT use using namespace std IN HEADER FILES! Preferably, don't use it at all.

Finally, learn to use your debugger as a comment mentioned.

Good luck.

Upvotes: 1

Related Questions