Author: Dave Gomboc
Date: 13:15:29 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. > >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. Caveat: That sounded like an insertion sort to me, not a bubble sort. >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. > >bruce Dave
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.