Join 136,902 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 1,737 people online right now. Registration is fast and FREE... Join Now!
I was watching a vid on Youtube where Eric Shmidt of Google asked Barack Obama, "what is the most efficient way of sorting a million 32 bit integers," and I'm curious to know what the answer was because Obama only said the "Bubble Sort" wasn't the most efficient way.
Just to give this thread a bit more substance, I would like to know more about this bubble sort from you guys.
Depends I suppose. Bubble sort is faster when the list is smaller and more prone to be in order to begin with. Other choices to sort the list include insertion sort or merge sort.
Depends I suppose. Bubble sort is faster when the list is smaller and more prone to be in order to begin with. Other choices to sort the list include insertion sort or merge sort.
From performance tests, and I could be remembering this wrongly, that quick sort is, as the name implies, usually the fastest sort you can do, especially with larger sets of numbers.
Edit: I guess I should also note however, that the quick sort has some worst case scenarios. Specifically when the list in in order or in reverse order. In these cases merge sort and heap sort, I believe, are actually faster.
This post has been edited by Einherjar: 18 Jul, 2008 - 11:36 AM
The question is very general, so I'm assuming we're talking about a simple sort with no requirements on insertion, deletion, or search times. If I'm sorting around 10 or fewer, I'll use insertion sort. If more than 10 and there are no strict memory limitations, I typically go for merge sort. If there are memory limitations then I might use heap sort or possibly quick sort.
This post has been edited by Programmist: 18 Jul, 2008 - 12:46 PM
Depends I suppose. Bubble sort is faster when the list is smaller and more prone to be in order to begin with. Other choices to sort the list include insertion sort or merge sort.
From performance tests, and I could be remembering this wrongly, that quick sort is, as the name implies, usually the fastest sort you can do, especially with larger sets of numbers.
Edit: I guess I should also note however, that the quick sort has some worst case scenarios. Specifically when the list in in order or in reverse order. In these cases merge sort and heap sort, I believe, are actually faster.
Of course, I was only mentioning a few off the top of my head. Parameters to the problem dictate what sort or search method to use.
Depends I suppose. Bubble sort is faster when the list is smaller and more prone to be in order to begin with. Other choices to sort the list include insertion sort or merge sort.
From performance tests, and I could be remembering this wrongly, that quick sort is, as the name implies, usually the fastest sort you can do, especially with larger sets of numbers.
Edit: I guess I should also note however, that the quick sort has some worst case scenarios. Specifically when the list in in order or in reverse order. In these cases merge sort and heap sort, I believe, are actually faster.
Of course, I was only mentioning a few off the top of my head. Parameters to the problem dictate what sort or search method to use.
Ah yes, I actually meant to quote the OP's post, and not yours Oops.
I have found that people like the quick sort. It is very popular but in technical applications you tend to see a preference for the merge sort.
with modern applications you may see concurrent algorithms used. These are generally derivatives of the quick sort or merge sort. While they may be "faster" they generally require the same number of comparisons and are therefor not really "more efficient".
Comparison searches can be no better than O(n*log(n)).
There are other specialized sorting algorithms which may be more efficient given some information about the data being sorted. A Radix sort for example has the potential to be very efficient for specialized situations.
Here is another good comparison of some sorting algorithms (as well as a nice list -- though not complete).
but i prefer quick sort. it is the quickest sorting method with efficient time and space.
Quick sort can be as fast as Merge sort [it is as fast as and not faster than Merge sort] but it's performance is not stable (goes up to O(n^2) in worst cases). Where as Merge sort is stable on performance O(n*log(n)). There are also few memory saving tricks for Merge sort. So I prefer Merge sort.
As NickDMax points out there are special sorts out there that provide more efficient searching than say quicksort, but these are not comparison based search algorithms.
I suspect that radix sort or bucket sort is the answer Eric was looking for.
Oops.
| 