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