Computer Science Canada Out of these algorithms |
| Author: | nemesest [ Sat Mar 04, 2006 3:56 pm ] |
| Post subject: | Out of these algorithms |
Bubble, selection, insertion, merge, quick sorts. Which is the fastest when the numbers are: ordered reversed random I'm trying to make an algorithm that looks at the sequence of the numbers and chooses the best algorithm but unfortunately I don't know which is the fastest in diff situations. |
|
| Author: | Clayton [ Sat Mar 04, 2006 6:36 pm ] |
| Post subject: | |
the selection sort is a horribly slow sort no matter what type of sort you use, while the bubble sort is relatively quick in all cases no matter what your sorting for |
|
| Author: | [Gandalf] [ Sat Mar 04, 2006 6:48 pm ] |
| Post subject: | |
What? Bubble sort is next slowest after selection sort, although it will be fast in the perfect situation (the elements are already ordered) because it will only go through each number once. Your best bet would be to go with quick sort, if you know it. |
|
| Author: | nemesest [ Sat Mar 04, 2006 8:01 pm ] | ||
| Post subject: | |||
I found out that for ordered numbers, bubble sort is the fastest. However, for random numbers, Quicksort is the fastest. So I decided to see the sequence of numbers. If 90% are sorted, I use bubble sort. If 90% are unsorted, I reverse the numbers and then use bubble sort. Otherwise, I use quicksort. In any case, could someone explain to me how quick and merge sort works and the differences between them? This is really bugging me. Thank you.
|
|||
| Author: | [Gandalf] [ Sat Mar 04, 2006 8:23 pm ] |
| Post subject: | |
For exactly how they work, I suggest another source, there's bound to be plenty on google. Here's a quick explanation: Merge sort divides the array to be sorted into 2, sorts both, then merges them back together. Quick sort is a bit more complicated... http://en.wikipedia.org/wiki/Quick_sort 90% probably isn't a good amount. Really, it should only be for 100% already sorted, since that 90% will begin to grow as you get larger and larger arrays being sorted. |
|
| Author: | nemesest [ Sat Mar 04, 2006 8:58 pm ] |
| Post subject: | |
I read over wikipedia and many other sites already but I couldn't grasp what was really going on. Divide in halves...divide in 2s...merge...etc. I don't get what these mean. |
|
| Author: | md [ Sat Mar 04, 2006 9:32 pm ] |
| Post subject: | |
Quicksort is the fastest or tied for fastest in all cases; so long as you are decently intelligent in your choice of pivot. |
|
| Author: | nemesest [ Sun Mar 05, 2006 9:02 am ] |
| Post subject: | |
But isnt quicksort slower than bubble sort when the numbers are sorted. |
|
| Author: | md [ Sun Mar 05, 2006 10:52 am ] |
| Post subject: | |
nemesest wrote: But isnt quicksort slower than bubble sort when the numbers are sorted.
Yes, sorry what I should have said is that quicksort is the best general purpose sorting algorithm. It is guarunteed to run in O(n log n), assuming you choose a proper pivot. There are cases where other sorts are better, however those are all much worse then quicksort if specific conditions are not met. |
|
| Author: | Delos [ Sun Mar 05, 2006 11:44 am ] |
| Post subject: | |
If you don't understand recursion, then QSort will never make any sense. Check out zylum's tuts in [Turing Tutorials] on it if you need to. Also, I'm not sure if I like your idea of optimization very much - it's very subjective, and when n->large you'll be adding a complete iteration of all elements to your overall sort time. This mightn't be the best thing to do. Now what happens with a case when you have large chunks of sorted numbers, interspersed between unsorted numbers; but those sets themselves are not in order? You'll select Bubble Sort but this will end up being horrible slow! (For a simple eg: {5, 6, 7, 8, 9, 2, 9, 4, 1, 2, 3, 4, 6, 11, 0, 1, 4, 5, 6, 8, 9}. I haven't actually run the tests, but this appears to be an inefficiently sorted-by-Bubble set of numbers. Try it, include a counter in your sort to count the number of iterations it takes to sort, then run this under your optimization. Then, run it under each of the other sorts. I'm curious to see the results.) |
|
| Author: | codemage [ Mon Mar 06, 2006 9:52 am ] |
| Post subject: | |
A site I use as a supplement when I teach sorts is here: math.hws.edu/TMCM/java/xSortLab/ It visually shows a few of the sorts happening, so you can see how they work, logically. It also shows you how efficient they are... which should lead you to the conclusion that bubblesort is essentially the worst sort method possible.  |
|