Sorting by insertion of leading elements (Q1096394): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:12, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sorting by insertion of leading elements |
scientific article |
Statements
Sorting by insertion of leading elements (English)
0 references
1987
0 references
Consider the operation on permutations consisting of removing the leading element and inserting it somewhere in the string. The number of such operations required to sort a permutation \(\sigma\) of \(\{\) 1,...,n\(\}\) into increasing order is n-k, where k is the largest integer such that the last k entries of \(\sigma\) form an increasing sequence. There is a deterministic version of the problem in which the leading element is always inserted into the position equal to its value, and the process ends when 1 reaches the front. The permutation requiring the greatest number of steps to termination is 23...n1, and it requires \(2^{n-1}-1\) steps.
0 references
sorting by insertion
0 references
pancake problem
0 references