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)
divideandconquer algorithms such as mergesort. However, insertion sort or
selection sort are both typically faster for small arrays (i.e. fewer than 1020 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  1219 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 worstcase, which is the classic case for general analysis, but if you're expecting nonworst 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 worstcase, which is the classic case for general analysis, but if you're expecting nonworst 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 almostsorted, reversesorted, alreadysorted, 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 almostsorted, reversesorted, alreadysorted, 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 almostsorted, reversesorted, alreadysorted, 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 almostsorted, reversesorted, alreadysorted, 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
