quote:Original post by blizzard999 Bubble sort and similar are O(N^2)...merge sort(quick sort) is O(NlogN). Quick sort is implemented in std (and also in C). Why bubble?
Both merge sort and quick sort are horrendous on small inputs. Who knows, he may have bizarre data that makes quick sort O(N^2) It's entirely possible bubble sort is faster for his application.
quote:Original post by caffeineaddict After i converted it over to structures I got it working quite well, i''d never used them before and found them to be quite enjoyable to use.
Wait until you start using classes - you''re going to have a blast!
"Absorb what is useful, reject what is useless, and add what is specifically your own." - Lee Jun Fan
"Absorb what is useful, reject what is useless, and add what is specifically your own." - Lee Jun Fan
quote:Original post by blizzard999 Bubble sort and similar are O(N^2)...merge sort(quick sort) is O(NlogN). Quick sort is implemented in std (and also in C). Why bubble?
on partially sorted data bubble sort is quicker, inversely on reverse sorted data bubble sort is hideously slow (even slower than on random data)
on partially sorted data bubble sort is quicker, inversely on reverse sorted data bubble sort is hideously slow (even slower than on random data)
you cant always use those rules in the real world
It depends...I dont see why one should reimplement an algorithm everytime he need it! However it is possible to ''optimize'' a quick sort with pointers instead of value-copy...obviosly if the array to be sorted is VERY short a bubble sort can be faster. But It''s not possible to think about optimizations before writing working code! And qsort is ready to be used!
quote:Original post by blizzard999 Bubble sort and similar are O(N^2)...merge sort(quick sort) is O(NlogN). Quick sort is implemented in std (and also in C). Why bubble?
Both merge sort and quick sort are horrendous on small inputs. Who knows, he may have bizarre data that makes quick sort O(N^2) It''s entirely possible bubble sort is faster for his application.
nope, the O-thing(dont remember how its called now) is the worst case, so nothing with O(n^2) for quicksort... (what about bottom-up-heapsort? wasnt it O(n) ???)
nope, the O-thing(dont remember how its called now) is the worst case, so nothing with O(n^2) for quicksort... (what about bottom-up-heapsort? wasnt it O(n) ???)
T2k
the "O-thing" is not the worse case, it's an upper bound. Quick sort is O(N^2) in the worse case - in the average (and best) case it's O(NLogN).
The only linear sort I know of is bucket sort, which isn't practical in most cases.
Big-O represents the complexity of an algorithm as the data set goes to infinity . Quick Sort''s worst case is indeed O(n2); it''s best/average case is O(n*log(n)). Merge Sort has O(n*log(n)) in best/worst/average case, but has 2n memory requirement (which can be troublesome). Bubble, Selection, and Insertion are O(n2) best-case.
For small data sets bubble, selection, and insertion are often faster than quick and merge (although if the set is numeric, a radix sort can be hella fast). Those algorithms (quick/merge) are very good on large datasets however.
There are no hard and fast rules as to what constitutes ''large'', and odds are that sorting that small an array is a negligible speed impact anyway. In this case, whatever is quickest and least error-pronbe to implement wins. std::sort and qsort are your friends here.
I'm not sure where on earth you get O(n^2) best case for bubble sort, on already sorted data bubblesort would be O(n) (scan through it once, make no changes so drop out early) - if there is only one item out of line then it would be O(2n), O(n^2) is worst case for bubble sort.
[edited by - Narcist on November 20, 2003 3:51:13 AM]
It's entirely possible bubble sort is faster for his application.
