Author: Oliver Roese
Date: 19:33:17 10/19/99
Go up one level in this thread
On October 19, 1999 at 12:22:49, Bruce Moreland wrote: >On October 18, 1999 at 17:28:12, Oliver Roese wrote: > >>BTW, by glancing through an older crafty version i stumpeld across a remarkable >>comment there. Dr. Hyatt says there, that Bubblesort has outperformed all other >>sortalgorithms for a particular sortproblem! >>This is amazing, since AFAIK Bubblesort is the one documented sort-algorithm >>that is theoretically dominated by any other documented sort-algorithm. >>Consequently it is doomed by many as the "poor-mans-sort." >>Since i assume Dr. Hyatt knows what he say, we have a counterexample. >>Is there a explanation to that? > >The explanation is that a high percentage of the time you only have to bubble up >the top move or two. You don't end up sorting the whole list. > But it doesnt do that. Look at "qiesce.c" or "nexte.c" or "next.c". They always sort the whole array. >If your goal is to create a sorting algorithm that puts the best element at the >top of the list, and it is allowable to leave the rest undisturbed, the best >algorithm is clearly the bubble sort. You just look through the elements and >move the top one to the top. > Thats not bubblesort! >If you do a more complicated sort, you may sort the list faster, but the work >will almost always be wasted. > >You can drive faster than you can run, but if you want to get to 7-11, and it's >only a block or two away, it might be faster to run, since it takes time to find >your keys, get in the car, start it, get out of the driveway, park at the 7-11, >and get out of your car. This is true, but already known from literature. The irritating point here was the usage of bubblesort instead of the highly favorated insertionsort. Oliver
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.