[idaebak]

Hi

i'm working in sorting 8 numbers randomly , i', using three types merge Θ(n log n) , selection Θ(n^2), bubble Θ(n^2)

which one is the best to use ?

which type is the easiest for my case ?

i read that once

" selection sort is greatly outperformed on larger arrays by Θ(n log n)
divide-and-conquer algorithms such as mergesort. However, insertion sort or
selection sort are both typically faster for small arrays (i.e. fewer than 10-20 elements)
. A useful optimization in practice for the recursive algorithms is to switch to insertion
sort or selection sort for "small enough" sublists. "

is that right .. selection sort is the best ??

[macosxnerd101]

*Moved to Computer Science*

Selection sort is the worst of these three. Insertion is more efficient than mergesort for smaller arrays, as you stated. Mergesort will always outperform the other two over the long haul though (large enough arrays).

[Ryano121]

Also worth noting that unless your are sorting hundreds/thousands of elements, you probably aren't going to see much of a noticeable performance difference.

[jon.kiparsky]

"Best" is a misnomer. Look at the text you cited. If speed is your primary concern, they scale differently. If you know the initial state, they will respond differently to different initial states.
Mergesort is probably the best in the worst-case, which is the classic case for general analysis, but if you're expecting non-worst cases, you might find another sort works best. That's why you're taking a class in data structures and analysis of algorithms, right?

Of course, the best sort is always the one that's built into the sort method of the data structure you're using, because it's already implemented for you, and you can just get on with whatever it is you're working on.

[idaebak]

i know that merge is better for large array only !

so bubble and selection have the same worst case time comlexity

so how can i know the best one of them ? * confused *

and i read the bubble is slower than selection cause of swapping ?

[jon.kiparsky]

The best way to know which is the best for one case or another would be to come up with data sets representing the cases and do some trials. One thing might be to increment one counter for each swap and another for each compare, another would be to use a timer. (use the system time for this)

Data sets you might consider would include almost-sorted, reverse-sorted, already-sorted, and different sizes of same. But it's your experiment, go wild. Come up with cases and see what they do - and try to make predictions based on what you know about the algorithms and the data.

[idaebak]

jon.kiparsky, on 31 July 2012 - 12:02 PM, said:

The best way to know which is the best for one case or another would be to come up with data sets representing the cases and do some trials. One thing might be to increment one counter for each swap and another for each compare, another would be to use a timer. (use the system time for this)

Data sets you might consider would include almost-sorted, reverse-sorted, already-sorted, and different sizes of same. But it's your experiment, go wild. Come up with cases and see what they do - and try to make predictions based on what you know about the algorithms and the data.

thanks a lot <3 ,, you really helped