A Heuristic to Accelerate In-situ Permutation Algorithms
In-situ permutation algorithms are algorithms to permute an array of items without using a second array. Few space is needed when one proceeds permuting along a cycle. Thus, those algorithms first search for one element called leader on each cycle of the permutation.Then they move the items cycle by cycle. A great fraction of the runtime is spent with testing whether elements are leaders. We present a simple to implement heuristic to accelerate the search for leaders and present performance gains for randomly chosen permutations on three algorithms.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten