The Hierarchy of Hereditary Sorting Operators

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21240/24:00374777

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

The Hierarchy of Hereditary Sorting Operators

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The Hierarchy of Hereditary Sorting Operators

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název statě ve sborníku

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

ISBN

978-1-61197-791-2

ISSN

—

e-ISSN

—

Počet stran výsledku

18

Strana od-do

1447-1464

Název nakladatele

SIAM

Místo vydání

PHILADELPHIA

Místo konání akce

Alexandria

Datum konání akce

7. 1. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001267398704004