Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Quicksort Python sorts faster than Bubblesort C++.


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


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.


Please provide the code and set of data. If C++ is 100x faster than Python this might not always be the case.


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).

http://en.wikipedia.org/wiki/Sorting_algorithm#Quicksort




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: