Sorting with a popqueue
In this work, the authors consider a new data structure for sorting permutations, which they call popqueue in analogy with a much older notion called the popstack. They consider two sorting algorithms on popqueues, \texttt{Min} and \texttt{Cons}. They first classify permutations which are sorted by these algorithms in one pass. They then consider sorting in two passes and show that \texttt{Cons} is a more natural sorting algorithm. The authors classify permutations that are sortable by \texttt{Cons} in terms of pattern avoidance. They end with determining possible outputs of \texttt{Cons}, permutations with sort to them, and enumeration questions.
- Enumerating permutations sortable by \(k\) passes through a pop-stack
- Fertility monotonicity and average complexity of the stack-sorting map
- Fertility numbers
- Generating trees and forbidden subsequences
- scientific article; zbMATH DE number 3722110 (Why is no real title available?)
- scientific article; zbMATH DE number 3492580 (Why is no real title available?)
- Preimages under the bubblesort operator
- Preimages under the Queuesort algorithm
- Sorting twice through a stack
- Sorting Using Networks of Queues and Stacks
- Sorting with pattern-avoiding stacks: the 132-machine
- Stack sorting with restricted stacks
- Stack-sorting, set partitions, and Lassalle's sequence
- The on-line encyclopedia of integer sequences
- Théorie géométrique des polynômes eulériens
- Two stacks in series: a decreasing stack followed by an increasing stack
- Two-stack-sorting with pop stacks
This page was built for publication: Sorting with a popqueue
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6551807)
