A heuristic to accelerate in-situ permutation algorithms (Q1603509)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A heuristic to accelerate in-situ permutation algorithms |
scientific article |
Statements
A heuristic to accelerate in-situ permutation algorithms (English)
0 references
14 July 2002
0 references
In-situ permutation algorithms permute an array of \(n\) items without using a second array. Little space is needed when one proceeds permuting along a cycle. Thus, those algorithms first search for one element called the 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.
0 references
Algorithms
0 references
Performance evaluation
0 references
Heuristics
0 references
Permutations
0 references