Sorting by insertion of leading elements
type: Item
instance of: scholarly article
title: Sorting by insertion of leading elements
zbMATH Open document ID: 0633.68060
DOI: 10.1016/0097-3165(87)90022-7
author: Martin Aigner
author: Douglas B. West
published in: Journal of Combinatorial Theory. Series A
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 05A99
zbMATH DE Number: 4031005
zbMATH Keywords: sorting by insertion
zbMATH Keywords: pancake problem
MaRDI profile type: Publication
full work available at URL: 0097-3165(87)90022-7
OpenAlex ID: W2043016253
cites work: Bounds for sorting by prefix reversal
description: scientific article; zbMATH DE number 4031005