And here's another interesting algorithm/structure: Randomized Slide to Front
H. S. Teoh via Digitalmars-d
digitalmars-d at puremagic.com
Mon Nov 30 14:00:25 PST 2015
On Mon, Nov 30, 2015 at 04:58:16PM -0500, Steven Schveighoffer via Digitalmars-d wrote:
> On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:
> >On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
> >>What about when element i is matched, swap it with the (i/2)'th element?
> >Randomization is essential - without it you have thrashing if you
> >search for 2 elements in alternation. -- Andrei
> What about selecting a random element in 0..k/2 instead of 0..k-1?
Or selecting the (i/k)'th element for k = uniform(1..i)?
People walk. Computers run.
More information about the Digitalmars-d