BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)

DOI10.1016/0304-3975(93)90364-YzbMATH Open0783.68060WikidataQ56049337 ScholiaQ56049337MaRDI QIDQ688722FDOQ688722

Ingo Wegener

Publication date: 12 December 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

• scientific article
• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• A variant of heapsort with almost optimal number of comparisons
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• QuickHeapsort: modifications and improved analysis

zbMATH Keywords

quicksortheapsortaverage case analysis of algorithms

Mathematics Subject Classification ID

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

Cites Work

• Quicksort
• Title not available (Why is that?)
• The analysis of Quicksort programs
• Increasing the efficiency of quicksort
• Title not available (Why is that?)
• Building heaps fast
• Average-case results on heapsort
• A variant of heapsort with almost optimal number of comparisons
• Deleting the root of a heap
• Title not available (Why is that?)
• An average case analysis of Floyd's algorithm to construct heaps

Cited In (17)

• The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
• Weak heaps engineered
• On sorting, heaps, and minimum spanning trees
• Heaps with bits
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• STRONGER QUICKHEAPS
• A lower bound for the worst case of bottom-up-heapsort
• Fat heaps without regular counters
• QuickHeapsort: modifications and improved analysis
• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons
• Heap construction: Optimal in both worst and average cases?
• Title not available (Why is that?)
• QuickXsort: a fast sorting scheme in theory and practice
• Optimizing binary heaps
• Multiway in-place merging
• Sorting using heap structure
• QuickHeapsort, an efficient mix of classical sorting algorithms

Uses Software

• Quicksort

This page was built for publication: BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)

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