Sorting by placement and shift

MaRDI QIDQ4633812zbMATH OpenFDO

Authors Sergi Elizalde, Peter Winkler

Publication date 6 May 2019

Full work available at URL https://arxiv.org/abs/0809.2957, https://dl.acm.org/citation.cfm?id=1496778

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Abstract: In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. (In fact, a special case of this algorithm is commonly used to hand-sort files.) However, it is not obvious that this algorithm necessarily terminates. We show that in fact the algorithm terminates after at most $2^{n-1}-1$ steps in the worst case (confirming a conjecture of L. Larson), and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation.

Recommendations

• Sorting by insertion of leading elements
• Two-dimensional homing sort
• Sorting a bridge hand
• The number of times the placement algorithm ends at the top and bottom
• An in-place sorting with O ( n log n ) comparisons and O ( n ) moves

Cited in

(9)

• Sorting by insertion of leading elements
• Two-dimensional homing sort
• How to sort by walking and swapping on paths and trees
• Jump home and shift: an acyclic operation on permutations
• The number of times the placement algorithm ends at the top and bottom
• Sorting with minimum data movement
• scientific article; zbMATH DE number 140497 (Why is no real title available?)
• A quadratic lower bound for topswops
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Sorting by placement and shift

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633812)