Fast and Simple Sorting Using Partial Information
dc.contributor.author
Hladík, Richard
dc.contributor.supervisor
Steurer, David
dc.contributor.supervisor
Haeupler, Bernhard
dc.date.accessioned
2024-07-22T08:05:07Z
dc.date.available
2024-07-22T07:20:32Z
dc.date.available
2024-07-22T08:05:07Z
dc.date.issued
2024-07
dc.identifier.uri
http://hdl.handle.net/20.500.11850/684133
dc.identifier.doi
10.3929/ethz-b-000684133
dc.description.abstract
We consider the problem of sorting n totally ordered items by doing binary comparisons, given a list of m comparisons that have already been performed. This problem has been called sorting under partial information, and it has been intensely studied since 1976.
We propose a simple algorithm that solves this problem in O(log T) comparisons and O(log T + n + m) time, where T is the number of total orders consistent with the pre-existing comparisons. This is optimal up to constant factors. This problem has a long line of research, and for more than 30 years, all known solutions were either not polynomial, or relied on the ellipsoid method, which made them impractical. The best previous result achieves O(log T) comparisons in Θ(n^2.5) time and is more complicated.
Our result combines two standard algorithms: topological sorting, and heapsort with the right kind of heap. Our algorithm can be obtained by a one-line modification of the topological sorting algorithm, and its analysis is short and straightforward.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
sorting under partial information
en_US
dc.subject
heaps
en_US
dc.subject
data structures
en_US
dc.subject
Beyond worst-case analysis
en_US
dc.subject
Graph algorithms
en_US
dc.title
Fast and Simple Sorting Using Partial Information
en_US
dc.type
Master Thesis
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.size
35 p.
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09622 - Steurer, David / Steurer, David::08730 - Gruppe Häupler / Group Häupler
en_US
ethz.relation.isSupplementedBy
https://doi.org/10.48550/arXiv.2404.04552
ethz.date.deposited
2024-07-22T07:20:33Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2024-07-22T08:05:13Z
ethz.rosetta.lastUpdated
2024-07-22T08:05:13Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Fast%20and%20Simple%20Sorting%20Using%20Partial%20Information&rft.date=2024-07&rft.au=Hlad%C3%ADk,%20Richard&rft.genre=unknown&rft.btitle=Fast%20and%20Simple%20Sorting%20Using%20Partial%20Information
Files in this item
Publication type
-
Master Thesis [2105]