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

Question

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.

Answer 1

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());

Answer 2

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