And here's another interesting algorithm/structure: Randomized Slide to Front

[Denis Koroskin via Digitalmars-d]

On Monday, 30 November 2015 at 22:11:09 UTC, deadalnix wrote:
> On Monday, 30 November 2015 at 21:50:09 UTC, 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
>
> 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).

Imagine that there are 1000 elements, 500th elements is X and 
1000th element is Y.

1) search for Y: Y is last, takes 1000 iterations, swaps X<->Y
2) search for X: X is last, takes 1000 iterations, swaps X<->Y
3) back to 1