The Hierarchy of Hereditary Sorting Operators

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493170" target="_blank" >RIV/00216208:11320/24:10493170 - isvavai.cz</a>

Alternative codes found

RIV/68407700:21240/24:00374777

Result on the web

<a href="https://doi.org/10.1137/1.9781611977912.59" target="_blank" >https://doi.org/10.1137/1.9781611977912.59</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611977912.59" target="_blank" >10.1137/1.9781611977912.59</a>

Result language

angličtina

Original language name

The Hierarchy of Hereditary Sorting Operators

Original language description

We consider the following general model of a sorting procedure: we fix a hereditary permutation class C, which corresponds to the operations that the procedure is allowed to perform in a single step. The input of sorting is a permutation pi of the set [n] = {1, 2, ...,, n} i.e., a sequence where each element of [n] appears once. In every step, the sorting procedure picks a permutation sigma of length n from C, and rearranges the current permutation of numbers by composing it with sigma. The goal is to transform the input pi into the sorted sequence 1, 2, ..., n in as few steps as possible. Formally, for a hereditary permutation class C and a permutation pi of [n], we say that C can sort pi in k steps, if the inverse of pi can be obtained by composing k (not necessarily distinct) permutations from C. The C-sorting time of pi, denoted st (C; pi), is the smallest k such that C can sort pi in k steps; if no such k exists, we put st (C; pi) = +infinity. For an integer n, the worst-case C-sorting time, denoted wst (C; n), is the maximum of st (C; pi over all permutations pi of [n]. This model of sorting captures not only classical sorting algorithms, like insertion sort or bubble sort, but also sorting by series of devices, like stacks or parallel queues, as well as sorting by block operations commonly considered, e.g., in the context of genome rearrangement. Our goal is to describe the possible asymptotic behavior of the function wst (C; n), and relate it to structural properties of C. As the main result, we show that any hereditary permutation class C falls into one of the following five categories: wst (C; n) = + infinity for n large enough, wst (C; n) = Theta(n(2)), Omega(root n) &lt;= wst (C; n) &lt;= O(n), Omega(log n) &lt;= wst (C; n) &lt;= O(log(2) n), or wst C; n) = 1 for all n &gt;= 2. In addition, we characterize the permutation classes in each of the five categories.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

PROCEEDINGS OF THE 2024 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA

ISBN

978-1-61197-791-2

ISSN

—

e-ISSN

—

Number of pages

18

Pages from-to

1447-1464

Publisher name

SIAM

Place of publication

PHILADELPHIA

Event location

Alexandria

Event date

Jan 7, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001267398704004