Skip to main content
replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link
#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 herehere and herehere 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;
}
#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;
}
#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;
}
Source Link
greatwolf
  • 1.9k
  • 2
  • 19
  • 23

#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;
}