Author: Dann Corbit
Date: 22:32:31 11/03/03
Go up one level in this thread
On November 04, 2003 at 00:49:30, Joel wrote: >Hey Dann, > >Had a glimpse of your code, and noticed the comment regarding the 'heart' of the >quicksort. Interesting... > >// If the sort is going quadratic, we switch to heap sort. > >Have you tried changing this rule to 'if sort is going quadratic, change the >pivot selection to random' and seeing whether the avoidance of heap sort's >overhead is worth it? It already does randomizing of the median. However, Bentley et. al. have formally proved that every form of quick sort has at least one case that makes it go quadratic. Hence, the invention of introspective sort. The perverse case is extremely unlikely, but incredibly unpleasant if it does occur.
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.