Steven D'Aprano wrote: > On Fri, 08 Feb 2008 19:09:06 -0800, Jeff Schwab wrote: > >> Steven D'Aprano wrote: >>> On Fri, 08 Feb 2008 17:00:27 -0800, t3chn0n3rd wrote: >>> >>>> Do you think it is relatively easy to write sort algorithms such as >>>> the common Bubble sort in Python as compared to other high level >>>> programming langauges >>> >>> You realise that bubble sort is one of the worst possible sort >>> algorithms possible, particularly on modern hardware? It's not the >>> worst: bogo sort and bozo sort are worse, but bubble sort is still >>> pretty atrocious. >> That's the conventional wisdom, mostly because CS professors need a "bad >> algorithm" to show undergrads, but it's not really accurate. The truth >> is that bubble-sort's performance depends strongly on the input data. In >> the worst case, yes, bubble-sort is O(n^2); however, for almost-sorted >> data (only a few elements out of place), bubble-sort is actually one of >> the fastest known algorithms. > > It depends on what you mean by "bubble sort". There are many different > variations of bubble sort, that are sometimes described by names such as > comb sort, cocktail sort, exchange sort, and sometimes merely referred to > bubble sort. It's rather like any divide-and-conquer sorting algorithm > being called quicksort. > > I'm as guilty of that as anyone else -- the example code I posted, raided > from Wikibooks is very different from this bubble sort algorithm from > PlanetMath: > > http://planetmath.org/encyclopedia/Bubblesort.html > > def bubblesort(L): > done = False > while not done: > done = True > for i in xrange(len(L)-1): > if L[i+1] <= L[i]: > L[i], L[i+1] = L[i+1], L[i] > done = False > return L > > This one runs significantly faster than the earlier one I posted. > > Another vital factor is, what language are you implementing the sort > routine in? The conventional wisdom for low-level languages like assembly > and C doesn't necessarily hold for high-level languages like Python. > Comparisons are slow in Python and fast in C; in C a good algorithm will > minimize the amount of moves, while in Python a good algorithm will > minimize the number of comparisons. > > Finally, what hardware are you running on? There are interactions between > hardware caches and pipes that can ruin the performance of an otherwise > promising algorithm. > > > But all those factors aside, I fear that your attempt to rehabilitate the > reputation of bubble sort is misplaced. Here's another person who wants > to defend bubble sort: > > "A fair number of algorithm purists (which means they've probably never > written software for a living) claim that the bubble sort should never be > used for any reason. Realistically, there isn't a noticeable performance > difference between the various sorts for 100 items or less, and the > simplicity of the bubble sort makes it attractive." > > http://linux.wku.edu/~lamonml/algor/sort/bubble.html > > But then on the same person's page on insertion sort: > > "The insertion sort is a good middle-of-the-road choice for sorting lists > of a few thousand items or less. The algorithm is significantly simpler > than the shell sort, with only a small trade-off in efficiency. At the > same time, the insertion sort is over twice as fast as the bubble sort > and almost 40% faster than the selection sort." > > http://linux.wku.edu/~lamonml/algor/sort/insertion.html > > He gives sample C code for both, and the bubble sort has eight lines of > code, versus nine for insertion sort (excluding bare braces). > > Perhaps what he should have said is: > > "Bubble sort is a tiny bit simpler than insertion sort, and almost twice > as slow!"
So basically, you and I agree that the right sorting algorithm for the job depends on the job. I have no particular interest in evangelizing for bubble-sort; however, I hate to see an algorithm (or data structure, or language, or programming style) taken out of the running before the race even starts, just because it's out of fashion. -- http://mail.python.org/mailman/listinfo/python-list
