8
\$\begingroup\$

Here is the implementation I ended up with. Please post your feedback!

#include <cstdio>
#include <cstdlib>

#include <iostream>

inline void swap(int * const a, const int i, const int j) {

    const int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void printArray(int *a, int len) {
    for(int i=0; i<len; i++)
        printf("%i ", a[i]);
    printf("\n");
}

void qsort(int * const a, const int len) {

    if(len < 2)
        return;

    const int pivot = a[rand() % len];

    printf("Choosed pivot %i\n", pivot);

    int lower = 0;
    int upper = len - 1;

    while(true) {

        while(a[lower] < pivot)
            lower++;

        while(a[upper] > pivot)
            upper--;

        printArray(a, len);

        if(lower == upper)
            break;

        swap(a, lower, upper);
    }

    printf("First Part ");
    printArray(a, lower);
    printf("Second Part ");
    printArray(a + lower + 1, len - lower - 1);
    printf("\n");

    qsort(a, lower);
    qsort(a + lower + 1, len - lower - 1);
}

int main() {

    int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
    int len = sizeof(a)/sizeof(int);

    qsort(a, len);
    printArray(a, len);

    std::cin.get();
}
\$\endgroup\$
  • 4
    \$\begingroup\$ It may be tagged C++ but this looks more like C code. You need to learn to utilize the standard library more. \$\endgroup\$ – Martin York Dec 12 '11 at 17:01
  • \$\begingroup\$ That improved code may be put into a self-answer instead, if further review is not needed. \$\endgroup\$ – Jamal Aug 8 '14 at 14:54
11
\$\begingroup\$
#include <cstdio>
#include <cstdlib>

#include <iostream>

If you're writing C++ prefer cout and cin provided by iostream. They provide much better type-safety compared to their C counterparts. OTOH, you can still use printf and scanf if you don't need the extra flexibility provided by C++ streams and you want to keep overhead to a minimal. At any rate, it doesn't make sense to include both headers here -- you're either using one or the other.


inline void swap(int *const a, const int i, const int j) 
// ...

You don't need to write your own swap. The standard library provides a fully working std::swap which you can call like this:

std::swap(a[lower], a[upper]);

Note that const isn't really adding anything here for your qsort prototype since everything's pass-by-value. A subtle point is that pointer *a below is also pass-by-value. Changing *a in qsort won't affect where the original 'a' pointers to(the one passed by main).

void qsort(int * const a, const int len)
// ...

This qsort signature is more reminiscence of a C-style function than C++. In C++ it's more common to accept a range to sort by templatizing the parameters with iterator types. Something more akin to this for example:

template <class RANDOMIT>
void qsort(RANDOMIT begin, const RANDOMIT &end);

This is well covered in other quicksort questions already. Take a look here and here for a more detailed explanation and other ideas you can explore.


I would also factor out the partitioning code to its own function just to keep the tasks well-defined.

while(true) {
    while(a[lower] < pivot)
        lower++;
    while(a[upper] > pivot)
        upper--;

    printArray(a, len);

    if(lower == upper)
        break;

    swap(a, lower, upper);
}

There's also a bug lurking above -- duplicate items will cause an infinite loop. A possible fix might be:

while(true) 
{
    // ...
    if(lower >= upper) break;

    if(a[lower] != a[upper]) { std::swap(a[lower], a[upper]); }
    ++lower, --upper;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the review! I know about iostream, however I hate the additional typing required to use it. \$\endgroup\$ – Nils Dec 12 '11 at 19:04
  • 1
    \$\begingroup\$ std::swap should rather be used as using std::swap; swap(x, y); - This will allow argument-dependent lookup to use user-defined overloads of swap in other namespaces. \$\endgroup\$ – UncleBens Dec 14 '11 at 22:47
  • \$\begingroup\$ Is there any reason why you did not suggest using std::partition? \$\endgroup\$ – Nobody moving away from SE Jul 28 '14 at 9:37
  • \$\begingroup\$ I did not know about std::partition, I really have to look into this. \$\endgroup\$ – Nils Jul 28 '14 at 14:48
  • \$\begingroup\$ I'm not seeing the bug in that code you say has one - care to point out what it is? \$\endgroup\$ – Ryan Aug 8 '14 at 16:59
7
\$\begingroup\$

I understand that passing the length around can be useful if you pass dynamic arrays to your functions, but you could still write some reusable helper functions to handle statically-sized arrays:

template<typename T, std::size_t N>
std::size_t size(const T(&)[N])
{
    return N;
}

With this function, you can write:

int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
int len = size(a);

You are using std::rand, but you don't seed it with std::srand first. Anyway, if you have a C++11 compiler, try to use the new <random> module instead. Standard methods that may use std::rand, such as std::random_shuffle are even deprecated in C++14.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

@Victor: Cover all the points I wanted:

So just one very minor not pick.

int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
int len = sizeof(a)/sizeof(int);

Prefer to define this in terms of the actual elements. Then if you change the type of the array you only need to change in one place:

int len = sizeof(a)/sizeof(a[0]); // a[0] will always have the correct type even if you
                                  // change the underlying type of the array. And since
                                  // is evaluated at compile time will always work.

Comment 1:

while(a[lower] < pivot)
    lower++;
while(a[upper] > pivot)
    upper--;

Which set do elements that are equal to the pivot go into?

Comment 2:

    if(lower == upper)
        break;

How often will that happen?

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

With C++11 and std::partition the code is waaay smaller and easier to read, I ended up with:

template <typename it_t>
void qsort(it_t begin, it_t end)
{
    typedef decltype(*begin) elem_t;

    size_t length = end - begin;

    if (length < 2)
    {
        return;
    }

    elem_t pivot = *(begin + ( rand() % length));

    it_t newPivotPos = partition(begin, end, [=] (elem_t elem) { return elem < pivot; });

    qsort(begin, newPivotPos);
    qsort(newPivotPos, end);
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Don't use decltype(*begin) to return the underlying type. decltype(*begin) doesn't behave the same as std::iterator_traits<it_t>::value_type (see a proxy class example of std::vector<bool>). Use std::distance to calculate the elements between iterators (still constant time for your random access iterators, linear time for others). If you are suggesting c++11, don't use rand(). Instead, write a random selector with the <random> library. Use PascalCase for user-defined class/type names (Iter_t, Elem_t). \$\endgroup\$ – Snowhawk Aug 10 '14 at 6:17
  • \$\begingroup\$ Thx for the comment! But the link to the proxy class example is broken. \$\endgroup\$ – Nils Aug 10 '14 at 11:36
  • \$\begingroup\$ However I do not understand why I should use distance instead of just minus is there any case where minus would not work? \$\endgroup\$ – Nils Aug 10 '14 at 11:45
  • \$\begingroup\$ @Nils std::distance is usable on InputIterator whereas operator - is only required for RandomAccessIterator. In short std::distance allows template code to function for a broader range of iterator types. \$\endgroup\$ – Emily L. Jan 8 '17 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.