Quick sort by choice Sort (Java vs C ++)

Question

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

Here are 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 have always been taught that QuickSort is the fastest. This is confirmed in Java, but in C ++ it completely closes.

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

I tried to support functions the same between languages, and they are exactly the same, except for using a vector in C ++ vs an int array. I would prefer to use a vector anyway, because the actual project that I want to use for sorting in C ++ requires a vector.

I am sure this is a dumb mistake or something that I am doing, but please provide some idea of ​​why this is happening.

EDIT:

In my opinion, I see what the problem is. Thanks to everyone for the very quick answers. I will modify my code to work as intended. I knew this was a simple mistake. In addition, although the question asked is rather confusing, the answers are educational.

Answer 1

The quicksort function returns the entire vector by value for each recursive call, even if the function changes it in place. Probably returning all these temporary situations, and then discarding them, his performance hurts.

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

EDIT: if you are more used to Java, where almost all links are garbage collected, note that in C ++ returning by value (as you have on the return type) usually makes a copy of what is returned. And as @Johannes Schaub-litb notes, the compiler is not even able to optimize the return, because it does not return an automatic (local) variable.

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

Answer 2

You return a full vector for each 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 is guaranteed as a quick sort (although this will ruin your profiling because you are not doing a true comparison).

EDIT:

Apparently std::sort does not guarantee fast sorting, but O (n * log (n)) is guaranteed to be. A source

Answer 3

There is another issue with your C ++ code that no one seems to have pointed out yet. If we get rid of the synchronization code, this will become pretty obvious, though:

 quicksort(A,0,length - 1); SelectionSort(A,length); 

You are sorting by already sorted data. In the circumstances, this probably doesn't matter much, but it still helps some. If you used insertion sort, it will appear almost instantly.

Answer 4

The problem is most likely related to your quicksort implementation. If you include the header and use std::sort - which is not a quick sort, but an introsort, an option that is designed to improve worst case performance, the results are completely different:

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

While working with your quicksort implementation, I get outputs similar to:

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

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

Answer 5

C ++ code crashes. First, the standard already provides quicksort- std::sort . Secondly, did you choose std::vector - for an array of static size? Thirdly, ftime , and the rest are invalid profiling timers. Thirdly, you save return values ​​from quicksort , even if the function accepts the link - if you did not set the optimization flags correctly, this can lead to performance loss.

 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.

Answer 6

I agree with Mark B

You must also make sure: - run each test yourself - run each test several times to get the average - use the same data for all tests

Answer 7

There are some problems with the code causing this. In the Java version, you sort the array you get, while in the C ++ version you sort the vector and return a copy of it (you make an unnecessary copy of each quick sort recursion).

Remember to compile a C ++ version with optimizations (-O3).

Answer 8

Mark B hits a nail on his head at this. I repeated the test with updated code on my installation with the results

Java QS: 7ms

Java SS: 111ms

against

C ++ QS: 1ms

C ++ SS: 72ms