Two Spectra of Self-Organizing Sequential Search Algorithms
Aaron M. Tenenbaum, Richard M. Nemes · SIAM Journal on Computing · 1982
Two sets of algorithms for searching and dynamic reorganization of linear lists are presented. Each set forms a spectrum, with the well-known move-to-front and transposition algorithms at the extrema. A linear ordering on the stationary expected search cost of the algorithms in each of the two spectra is established over a restricted set of probability distributions.