A variant of heapsort with almost optimal number of comparisons

DOI10.1016/0020-0190(87)90142-6MaRDI QIDQ1108015zbMATH OpenOpenAlexWikidataFDO

Authors Svante Carlsson

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90142-6

zbMATH Keywords

sortingheapsort

Mathematics Subject Classification ID

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

Recommendations

• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons
• A Note on HEAPSORT
• Sorting using heap structure
• scientific article; zbMATH DE number 1444318

Cites work

• scientific article; zbMATH DE number 4088895 (Why is no real title available?)
• scientific article; zbMATH DE number 3763287 (Why is no real title available?)
• Improving worst-case behavior of heaps

Cited in

(23)

• Average-case results on heapsort
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• On sorting, heaps, and minimum spanning trees
• Recurrence relations on heaps
• Worst-case analysis of generalized heapsort algorithm revisited
• Heaps with bits
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• The Analysis of Heapsort
• An optimal algorithm for deleting the root of a heap
• A Simple Modification of Xunrang and Yuzhang'S HEAPSORT Variant Improving its Complexity Significantly
• Implementing HEAPSORT with ( n log n - 0.9 n ) and QUICKSORT with ( n log n + 0.2 n ) comparisons
• An in-place priority queue with \(O(1)\) time for push and \(\lg n + O(1)\) comparisons for pop
• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons
• A Note on HEAPSORT
• Heap construction: Optimal in both worst and average cases?
• Almost-sure asymptotics for the number of heaps inside a random sequence
• Worst-case analysis of a generalized heapsort algorithm
• Best case lower bounds for heapsort
• Optimizing binary heaps
• Sorting using heap structure
• QuickHeapsort, an efficient mix of classical sorting algorithms
• Worst-case efficient sorting with QuickMergesort

This page was built for publication: A variant of heapsort with almost optimal number of comparisons

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