Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons

DOI10.1007/S00453-012-9696-5MaRDI QIDQ476439zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael T. Goodrich

Publication date 2 December 2014

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://europepmc.org/articles/pmc3925461

zbMATH Keywords

randomized algorithmssortingChernoff boundsoblivious algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• Randomized Shellsort, a simple oblivious sorting algorithm
• Randomized shellsort: a simple data-oblivious sorting algorithm
• Algorithms – ESA 2005
• Sorting, Approximate Sorting, and Searching in Rounds
• Randomized adaptive sorting
• Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms
• scientific article; zbMATH DE number 861443
• An approximation algorithm for sorting by reversals and transpositions

Cites work

• scientific article; zbMATH DE number 4048925 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 108391 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Lower Bound on the Size of Shellsort Sorting Networks
• A lower bound on the average-case complexity of shellsort
• Algorithm design: Foundations, analysis, and Internet examples
• Analysis of Shellsort and related algorithms
• Analyzing variants of Shellsort
• Bad cases for shaker-sort
• Computing with Noisy Information
• Fault Tolerant Sorting Networks
• Fun-Sort -- or the chaos of unordered binary search
• Hypercubic Sorting Networks
• Improved sorting networks with O(log N) depth
• Improved upper bounds on Shellsort
• Introduction to algorithms
• Lower Bounds for Shellsort
• Noisy sorting without resampling
• Probability and Computing
• Quicksort
• Randomized Shellsort, a simple oblivious sorting algorithm
• Secure multi-party computation made simple
• Sorting in \(c \log n\) parallel steps
• Sorting networks of logarithmic depth, further simplified
• Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms
• The coupon-collector problem revisited — a survey of engineering problems and computational methods
• Universally composable two-party and multi-party secure computation

Cited in

(3)

• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• Randomized shellsort: a simple data-oblivious sorting algorithm
• Randomized Shellsort, a simple oblivious sorting algorithm

Describes a project that uses

Uses Software

• Quicksort
• FairplayMP

This page was built for publication: Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476439)