Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons

Details Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons

2010-11-10

arxiv.org/abs/1011.2480v1

Computer Science

Data Structures and Algorithms

Full version of a paper appearing in ANALCO 2011, in conjunction with SODA 2011

Scientific paper

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 \emph{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 $\Omega(n^2\log n)$ expected time in order to succeed, and that in $O(n^2\log n)$ time this algorithm succeeds with high probability for any input. We also show there is an implementation of Annealing sort that runs in $O(n\log n)$ time and succeeds with very high probability.

Affiliated with

Also associated with

No associations

Rating

Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-429648