Quicksort for ints

Question

I have written the following quicksort without using online help. It seems to be fine, but is there anything to improve?

#include<iostream>

using namespace std;
void quicksort(int*, int, int);
void print(int *p, int n)
{
    for(int i=0; i < n; ++i)
        cout << p[i] << ' ' ;
    cout << endl;
}
int main()
{
    int arr[] = {10,10,15,15,23,5,55,8,6,0,32,10,100};
    int len = sizeof(arr)/sizeof(int);

    cout << "Before sort:\n";
    print(arr,len);
    quicksort(arr,0,len-1);

    cout << "After sort:\n";
    print(arr,len);
}

void quicksort(int *arr, int start, int end)
{
    if(start >= end)
        return;
    int pivot = arr[end];

    int i=start,j=start;
    for(;j < end; ++j)
        if(arr[j] < pivot)
        {
            swap(arr[i],arr[j]);
            ++i;
        }
    swap(arr[i],arr[end]);

    quicksort(arr,0,i-1);
    quicksort(arr,i+1,end);
}

Answer 1

1. Don't use using namespace std;

1. You should place explicit using statements like

   using std::cout;
   using std::swap;
   // etc.
   

   instead.

2. Here's some good argumentation why you shouldn't:
   Why is “using namespace std;” considered bad practice?

2. Don't use recursion

Using recursive calls limits you to the stack size, and may easily overflow on a large number of array elements.
You can use a loop and a std::stack<int> instead: - Entering the recursive function can be turned into a push() operation within the loop - Returning from the function can be turned in to geting the value via top() and a subsequent pop() operation.

3. Don't use raw c-style arrays with c++

Instead of using int arr[] you should use std::vector<int>, or a std::array<int,N> where N is a fixed size known at compile time.

Raw arrays have several drawbacks. The worst is that the size cannot longer be determined after they decayed to pointers if they're going out of scope.
Also raw array's aren't automatically copyable.

Answer 2

The code is very C-style. It accepts raw arrays. Indexes should not be of type int. Closed intervals are unidiomatic in C++. Since this is C++ code, use iterators and STL containers instead.

It may also be a good idea to randomize the choice of the pivot value to avoid the dead case of already sorted array. This can be done by swapping the last element with another randomly selected element before partitioning.

Answer 3

It's a relatively basic quicksort with no "fancy features", so it has the same issues that basic quicksort always has:

• O(n) space usage. When using recursion, that easily means "unexpected termination". When using an explicit stack, it means potentially wasting a ton of memory. The solution is to use recursion (or emulated recursion, with the explicit stack) only for the smallest half of the partition, and loop (tail recursion) for the larger half.

• O(n²) time in common cases. Picking the last (or first) element as the pivot has bad behavior for common inputs. Picking the middle element is easy and at least a little better, there are more advanced options such as median-of-3 etc. In most cases the O(n²) worst case stays, for example with the famous "median of 3 killer sequence", but a rare worst case has less impact than a common worst case.

• Inefficient partitioning (Lumoto's scheme). Hoare's original partioning scheme on average performs 1/3rd as many swaps. It is more complicated to code, but partitioning is the heart of quicksort: efficient partitioning is what makes quicksort quick.