Fast and Simple Sorting Using Partial Information
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909013730394112 |
|---|---|
| author | Haeupler, Bernhard Hladík, Richard Iacono, John Rozhon, Vaclav Tarjan, Robert Tětek, Jakub |
| author_facet | Haeupler, Bernhard Hladík, Richard Iacono, John Rozhon, Vaclav Tarjan, Robert Tětek, Jakub |
| contents | We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of total orders consistent with the pre-existing comparisons.
Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $O(\log T)$ on the number of comparisons has a time bound of $O(n^{2.5})$ and is more complicated.
Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-$k$ sorting problem: Given $k$ and the outcomes of some pre-existing comparisons, output the smallest $k$ items in sorted order. The modified algorithm solves the top-$k$ sorting problem in minimum time and comparisons, to within constant factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04552 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast and Simple Sorting Using Partial Information Haeupler, Bernhard Hladík, Richard Iacono, John Rozhon, Vaclav Tarjan, Robert Tětek, Jakub Data Structures and Algorithms F.2.2; G.2.2 We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $O(\log T)$ on the number of comparisons has a time bound of $O(n^{2.5})$ and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-$k$ sorting problem: Given $k$ and the outcomes of some pre-existing comparisons, output the smallest $k$ items in sorted order. The modified algorithm solves the top-$k$ sorting problem in minimum time and comparisons, to within constant factors. |
| title | Fast and Simple Sorting Using Partial Information |
| topic | Data Structures and Algorithms F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2404.04552 |