And here's another interesting algorithm/structure: Randomized Slide to Front
deadalnix via Digitalmars-d
digitalmars-d at puremagic.com
Mon Nov 30 14:11:05 PST 2015
On Monday, 30 November 2015 at 21:50:09 UTC, Andrei Alexandrescu
> 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
You'd end up swaping the 2 element in front, but keep them both
in front, so that sounds like it would have the same behavior as
the randomized algorithm.
Where it gets hairy, is when you access 2 elements in the array
that would swap each other without getting in the front (because
they are at 2n and 2n + 1 with n big).
More information about the Digitalmars-d