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

#1 idaebak  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 17-April 12

question about sorting , which better to use in ..

Posted 31 July 2012 - 11:34 AM

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

Is This A Good Question/Topic? 0
  • +

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

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10771
  • View blog
  • Posts: 40,102
  • Joined: 27-December 08

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).
Was This Post Helpful? 0
  • +
  • -

#3 Ryano121  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1363
  • View blog
  • Posts: 3,002
  • Joined: 30-January 11

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.
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,540
  • Joined: 19-March 11

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.
Was This Post Helpful? 0
  • +
  • -

#5 idaebak  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 17-April 12

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 ?
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7950
  • View blog
  • Posts: 13,540
  • Joined: 19-March 11

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.
Was This Post Helpful? 2
  • +
  • -

#7 idaebak  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 17-April 12

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

Posted 31 July 2012 - 12:08 PM

View Postjon.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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1