Quick Sort vs Selection Sort (Java vs C++)

I created two projects. One in C++ and one in Java. I did time trials for a QuickSort and SelectionSort for both. Oddly enough I found some very strange behavior.

Here were the results for an array of size 10,000:

SelectionSort Java: 80 ms

SelectionSort C++: 2914 ms

QuickSort Java: 1 ms

QuickSort C++: ~45 seconds

Now call me crazy but I've always been taught that QuickSort is the fastest. This proves to be true in Java yet in C++ it completely gets shut down.

So my question is, does C++ handle QuickSort differently?

I tried to keep the functions the same between languages and they are exactly the same with the exception of using a vector in C++ vs an int array. I'd prefer to use a vector anyway because the actual project I want to use the sort for in C++ requires a vector.

I'm sure it's a dumb mistake or something I'm making but please provide some insight as to why this is happening.

EDIT:

I believe I see what the problem is. Thanks everyone for the extremely fast responses. I'll be modifying my code to work as intended. I knew it was a simple mistake. Also, although the question asked is quite embarrassing, the responses are educational.

Your quicksort function returns your entire vector by value on every recursive call, even though the function modifies it in place. Probably returning all those temporaries and then throwing them away hurts performance.

Just change the function to void and remove the ending return and see how it behaves.

EDIT: If you're more used to Java where almost everything is garbage collected references, note that in C++ a return by value (as you have on the return type) typically makes a copy of whatever is being returned. And as @Johannes Schaub - litb points out the compiler isn't even able to optimize the return away because it's not returning an automatic (local) variable.

EDIT2: If you aren't doing this as an exercise however you should use either std::sort or std::stable_sort (the latter if you know your data will already be almost sorted, or you need to preserve the order of duplicates). For example std::sort(A.begin(), A.end());

You are returning a complete vector on every recursive call. This takes a lot of time (99,99% of the time spent copying).

By the way, you can use the STL sort function in C++, it's guaranteed to be a quicksort (though this will mess up your profiling because you're not doing a true comparison).

EDIT:

Apparently std::sort is not guaranteed to be quicksort, but it is guaranteed to be O(n*log(n)). Source

There's yet another issue with your C++ code that nobody seems to have pointed out yet. If we get rid of the timing code, it becomes pretty obvious though:

quicksort(A,0,length - 1);

SelectionSort(A,length);

You're doing the selection sort on data that's already sorted. Under the circumstances, it probably doesn't make a huge difference, but still helps some. If you used an insertion sort, it would show up as practically instantaneous.

The issue is most probably related to your implementation of quicksort. If you include the header and use std::sort --which is not quicksort, but introsort, a variant that is meant to improve the worse case performance the results are quite different:

$ ./CompareSorts 
Quick Sort Took: 1
Selection Sort Took: 101

While running with your implementation of quicksort I am getting outputs similar to:

$ ./CompareSorts 
Quick Sort Took: 41
Selection Sort Took: 95

The hardware is a Core2-Duo 2GHz, and I compiled with g++ -O3 -o CompareSorts CompareSorts.cpp (note that the -O3 is important: it tells gcc to optimize as much as it can).

Your C++ code is fail. Firstly, the Standard already provides a quicksort- std::sort. Secondly, you picked a std::vector- for a statically sized array? Thirdly, ftime and the rest are not valid profiling timers. Thirdly, you keep returning values from quicksort, even though the function takes a reference- if you didn't set the optimization flags correctly this could destroy performance.

int main()
{
    std::vector<int> A(array_size);

    for(int i = 0; i < array_size; i++)
    {
        A[i] = rand() % array_size;
    }

    __int64 begin, end, frequency;
    QueryPerformanceFrequency((LARGE_INTEGER*)&frequency);
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    std::sort(std::begin(A), std::end(A));
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    std::cout << "Quick Sort Took: " << ((double)(end - begin) / frequency) * 1000 << std::endl;
    std::cin.get();

    return 0;
}

0.7ms.

I agree with Mark B

You should also make sure : - run each test on its own - run each test several time to get an average - use the same data for all the tests

There are some problems with your code causing this. In the Java version, you sort the array you receive while in the C++ version you sort the vector AND return a copy of it (you make an unecessary copy each recursion of the quicksort).

Don't forget to compile the C++ version with optimization (-O3).

Mark B hit the nail on the head in this one. I repeated the test with the updated code on my rig with the results

Java QS: 7ms

Java SS: 111ms

vs

C++ QS: 1ms

C++ SS: 72ms