Re:Google paper comparing performance of C++, Java, Scala, a...
by swah on Friday June 03, 2011 @07:12AM
(#2615898)
Quicksort Python sorts faster than Bubblesort C++.
[ Parent
| on HN ]
Re:Google paper comparing performance of C++, Java, Scala, a...
by amalcon on Friday June 03, 2011 @09:08AM
(#2616164)
In the average case for large datasets. Quicksort is O(n^2) worst-case (choosing the worst pivots possible), and Bubblesort is O(n) in the best case (e.g. an already-sorted array).
The C++ Bubblesort will have better worst-case and best-case performance, but worse average-case performance, for large inputs.
But this is all irrelevant, because in Python, you'll be using Timsort[1], which I'm pretty sure is implemented in C anyway. In C++, you'll be using std::sort unless you have a template allergy. If you use the Gnu stuff, that will be Introsort[2]; if MSVC, Quicksort.
[1]http://en.wikipedia.org/wiki/Timsort [2]http://en.wikipedia.org/wiki/Introsort
Re:Google paper comparing performance of C++, Java, Scala, a...
by BrandonM on Friday June 03, 2011 @12:10PM
(#2616896)
Python doesn't even use quicksort. It uses timsort (http://en.wikipedia.org/wiki/Timsort), which is a hybrid merge/insertion sort. It's also used to sort arrays in two different versions of Java. In other words, it's one of the fastest-known sorting algorithms.
Re:Google paper comparing performance of C++, Java, Scala, a...
by melling on Friday June 03, 2011 @08:43AM
(#2616091)
Please provide the code and set of data. If C++ is 100x faster than Python this might not always be the case.
Re:Google paper comparing performance of C++, Java, Scala, a...
by melling on Friday June 03, 2011 @09:35AM
(#2616257)
Down voted because people think Quicksort always wins in Python vs. a Bubble sort in C++? Wish I had time to find a case where that's not true. I'll point out that in the worst case, Quicksort is O(n^2).