One of the ``problèmes plaisants et délectables by Claude Berge (Un des ``problèmes plaisants et délectables de Claude Berge).

DOI10.1016/J.DISC.2005.12.027MaRDI QIDQ2433697zbMATH OpenOpenAlexFDO

Authors Antoine Deza, David Avis

Publication date 30 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.12.027

zbMATH Keywords

complexityoptimal algorithmsorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Review text

This paper studies the following sorting problem (using a slightly different statement), originally proposed by Claude Berge in the 1960's. Input: \(\lceil n/2\rceil\) black and \(\lfloor n/2\rfloor\) white balls, placed alternatively in a one-dimensional board consisting of an infinite number of cells (the first ball is black). Operation allowed: move two adjacent pairs of balls (keeping their relative order). Output: all white balls are placed consecutively, followed by all black balls. The authors show that the minimum number of moves needed to sort these balls is equal to \(\lceil n/2\rceil\) for \(n\geq5\).

Recommendations

• On the generalized Berge sorting conjecture
• Berge sorting
• STACS 2005
• A lemma and a conjecture on the cost of rearrangements
• Efficient algorithms for sorting k-sets in bins

Cites work

• Berge sorting

Cited in

(2)

• On the generalized Berge sorting conjecture
• Berge sorting

This page was built for publication: One of the ``problèmes plaisants et délectables by Claude Berge (Un des ``problèmes plaisants et délectables de Claude Berge).

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