Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl - Flip-sort and combinatorial aspects of pop-stack sorting

dmtcs:6196 - Discrete Mathematics & Theoretical Computer Science, April 30, 2021, vol. 22 no. 2, Permutation Patterns 2019 - https://doi.org/10.46298/dmtcs.6196
Flip-sort and combinatorial aspects of pop-stack sorting

Authors: Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl

    Flip-sort is a natural sorting procedure which raises fascinating combinatorial questions. It finds its roots in the seminal work of Knuth on stack-based sorting algorithms and leads to many links with permutation patterns. We present several structural, enumerative, and algorithmic results on permutations that need few (resp. many) iterations of this procedure to be sorted. In particular, we give the shape of the permutations after one iteration, and characterize several families of permutations related to the best and worst cases of flip-sort. En passant, we also give some links between pop-stack sorting, automata, and lattice paths, and introduce several tactics of bijective proofs which have their own interest.


    Volume: vol. 22 no. 2, Permutation Patterns 2019
    Section: Special issues
    Published on: April 30, 2021
    Accepted on: April 7, 2021
    Submitted on: March 12, 2020
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05A05, 05A19, 05A15, 05A16

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo ARXIV 2103.04332
    Source : ScholeXplorer IsRelatedTo DOI 10.37236/10334
    Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.2103.04332
    • 2103.04332
    • 10.37236/10334
    • 10.48550/arxiv.2103.04332
    Sorting by shuffling methods and a queue

    Consultation statistics

    This page has been seen 475 times.
    This article's PDF has been downloaded 236 times.