3 ms·
Quicksort Python sorts faster than Bubblesort C++.
by swah 15y ago
Quicksort Python sorts faster than Bubblesort C++.
- melling 15y agoPlease provide the code and set of data. If C++ is 100x faster than Python this might not always be the case.
- melling 15y agoDown 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 http://en.wikipedia.org/wiki/Sorting_algorithm#Quicksort
- amalcon 15y agoIn 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 http://en.wikipedia.org/wiki/Timsort [2]http://en.wikipedia.org/wiki/Introsort http://en.wikipedia.org/wiki/Introsort
- BrandonM 15y agoPython doesn't even use quicksort. It uses timsort (http://en.wikipedia.org/wiki/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.