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 ??

## 6 Replies - 1289 Views - Last Post: 31 July 2012 - 12:08 PM

##
**Replies To:** question about sorting , which better to use in ..

### #2

## Re: question about sorting , which better to use in ..

Posted 31 July 2012 - 11:41 AM

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

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

### #3

## Re: question about sorting , which better to use in ..

Posted 31 July 2012 - 11:44 AM

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.

### #4

## Re: question about sorting , which better to use in ..

Posted 31 July 2012 - 11:48 AM

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

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.

### #5

## Re: question about sorting , which better to use in ..

Posted 31 July 2012 - 12:00 PM

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 ?

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 ?

### #6

## Re: question about sorting , which better to use in ..

Posted 31 July 2012 - 12:02 PM

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.

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.

### #7

## Re: question about sorting , which better to use in ..

Posted 31 July 2012 - 12:08 PM

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.

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

Page 1 of 1