A framework for adaptive sorting

DOI10.1016/0166-218X(93)E0160-ZMaRDI QIDQ1891925zbMATH OpenFDO

Authors Ola Petersson, Alistair Moffat

Publication date 6 June 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(93)E0160-Z

zbMATH Keywords

presortednesssorting algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics of partially ordered sets (06A07) Searching and sorting (68P10)

Recommendations

• A framework for adaptive sorting
• A general method for improving insertion-based adaptive sorting
• Measures of Presortedness and Optimal Sorting Algorithms
• scientific article; zbMATH DE number 3943040
• A new measure of presortedness

Cites work

• A new measure of presortedness
• Adaptive Heapsort
• Encroaching lists as a measure of presortedness
• Exploiting partial order with Quicksort
• HISTORICAL SEARCHING
• How good is the information theory bound in sorting?
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 4213426 (Why is no real title available?)
• scientific article; zbMATH DE number 4155867 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 3614186 (Why is no real title available?)
• scientific article; zbMATH DE number 3997796 (Why is no real title available?)
• Measures of Presortedness and Optimal Sorting Algorithms
• Smoothsort, an alternative for sorting in situ
• Sorting shuffled monotone sequences
• Sorting, trees, and measures of order
• Splitsort -- an adaptive sorting algorithm
• Sublinear merging and natural mergesort

Cited in

(29)

• Splitsort -- an adaptive sorting algorithm
• Presorting algorithms: an average-case point of view
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• A new measure of presortedness
• Adaptive search over sorted sets
• Sublinear merging and natural mergesort
• Adaptive sorting: an information theoretic perspective
• An adaptive generic sorting algorithm that uses variable partitioning^∗
• Generating nearly sorted sequences -- the use of measures of disorder
• From time to space: fast algorithms that yield small and fast data structures
• Extensible Datasort Refinements
• Measures of Presortedness and Optimal Sorting Algorithms
• scientific article; zbMATH DE number 4213426 (Why is no real title available?)
• scientific article; zbMATH DE number 3943040 (Why is no real title available?)
• Randomized adaptive sorting
• Computing and ranking measures of presortedness
• Adaptive Heapsort
• Adaptive linear list reorganization under a generalized query system
• A general method for improving insertion-based adaptive sorting
• scientific article; zbMATH DE number 1444317 (Why is no real title available?)
• A framework for adaptive sorting
• Adaptive Shivers Sort: An Alternative Sorting Algorithm
• On the adaptiveness of Quicksort
• Chunky and equal-spaced polynomial multiplication
• Efficient Sorting in a Dynamic Adverse-Selection Model
• Sorting by Merging or Merging by Sorting?
• On partitions and presortedness of sequences
• Efficient sample sort and the average case analysis of PEsort

This page was built for publication: A framework for adaptive sorting

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