Randomized adaptive sorting

DOI10.1002/RSA.3240040103MaRDI QIDQ4034707zbMATH OpenOpenAlexFDO

Authors Vladimir Estivill-Castro, D. Wood

Publication date 16 May 1993

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240040103

zbMATH Keywords

adaptive sortingMerge SortQuicksortrandomized algorithmsSkip Sortsorting algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A framework for adaptive sorting
• A framework for adaptive sorting
• Algorithms – ESA 2004
• scientific article; zbMATH DE number 494377
• A general method for improving insertion-based adaptive sorting
• Increasing the Efficiency of Existing Sorting Algorithms by Using Randomized Wrappers
• An optimal parallel adaptive sorting algorithm

Cites work

• A List Insertion Sort for Keys With Arbitrary Key Distribution
• A new measure of presortedness
• Encroaching lists as a measure of presortedness
• Exploiting partial order with Quicksort
• scientific article; zbMATH DE number 4213426 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Measures of Presortedness and Optimal Sorting Algorithms

Cited in

(27)

• A select and insert sorting algorithm
• Fun-Sort -- or the chaos of unordered binary search
• Sorting by shuffling methods and a queue
• Extensions of self-improving sorters
• An adaptive generic sorting algorithm that uses variable partitioning^∗
• scientific article; zbMATH DE number 4213426 (Why is no real title available?)
• Running time of the treapsort algorithm
• Increasing the Efficiency of Existing Sorting Algorithms by Using Randomized Wrappers
• THE SHUFFLING BUFFER
• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• scientific article; zbMATH DE number 1857638 (Why is no real title available?)
• Introspective sorting and selection revisited
• Sorting shuffled monotone sequences
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Adaptive Shivers Sort: An Alternative Sorting Algorithm
• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• Quadratic time algorithms appear to be optimal for sorting evolving data
• On the adaptiveness of Quicksort
• Randomized shellsort: a simple data-oblivious sorting algorithm
• Randomized Shellsort, a simple oblivious sorting algorithm
• Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms
• Algorithms – ESA 2004
• Automata, Languages and Programming
• Fragile complexity of adaptive algorithms
• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence
• Efficient sorting during repetitive statistical computations: Algorithms and an application
• Computing inversion pair cardinality through partition-based sorting

This page was built for publication: Randomized adaptive sorting

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