Treffer: Spin-the-Bottle Sort and Annealing Sort: Oblivious Sorting via Round-Robin Random Comparisons

Title:
Spin-the-Bottle Sort and Annealing Sort: Oblivious Sorting via Round-Robin Random Comparisons
Authors:
GOODRICH, Michael T
Source:
Algorithmica. 68(4):835-858
Publisher Information:
Heidelberg: Springer, 2014.
Publication Year:
2014
Physical Description:
print, 42 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Organisation des mémoires. Traitement des données, Memory organisation. Data processing, Gestion des mémoires et des fichiers (y compris la protection et la sécurité des fichiers), Memory and file management (including protection and security), Algorithme randomisé, Randomized algorithm, Algoritmo aleatorizado, Approche probabiliste, Probabilistic approach, Enfoque probabilista, Borne Chernoff, Chernoff bound, Límite Chernoff, Confidentialité, Confidentiality, Confidencialidad, Gestion mémoire, Storage management, Gestión memoria, Permutation, Permutación, Plan randomisé, Randomized design, Plan aleatorizado, Recuit, Annealing, Recocido, Sécurité informatique, Computer security, Seguridad informatica, Triage, Sorting, Tría, Algorithme sans mémoire, Oblivious algorithm, Algoritmo sin Memória, Chernoff bounds, Oblivious algorithms, Randomized algorithms
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
Dept. of Computer Science, University of California, Irvine, Irvine, CA 92697-3435, United States
ISSN:
0178-4617
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=28568802
Rights:
Copyright 2015 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.28568802
Database:
PASCAL Archive

Weitere Informationen

We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by a temperature parameter. Both algorithms are simple, randomized, data-oblivious sorting algorithms, which are useful in privacy-preserving computations, but, as we show, Annealing sort is much more efficient. We show that there is an input permutation that causes Spin-the-bottle sort to require Ω (n2 log n) expected time in order to succeed, and that in O(n2 log n) time this algorithm succeeds with high probability for any input. We also show there is a specification of Annealing sort that runs in O(n log n) time and succeeds with very high probability.