QuickHeapsort, an efficient mix of classical sorting algorithms
type: Item
instance of: scholarly article
title: QuickHeapsort, an efficient mix of classical sorting algorithms
zbMATH Open document ID: 1016.68042
DOI: 10.1016/S0304-3975(01)00288-2
published in: Theoretical Computer Science
publication date: 2002-08-05T00:00:00Z
review text: We present an efficient and practical algorithm for the internal sorting problem. Our algorithm works in-place and, on the average, has a running-time of \(O(n \log n)\) in the size \(n\) of the input. More specifically, the algorithm performs \(n\log n+2.996n+o(n)\) comparisons and \(n\log n+2.645n+o(n)\) element moves on the average. An experimental comparison of our proposed algorithm with the most efficient variants of Quicksort and Heapsort is carried out and its results are discussed.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1776345
zbMATH Keywords: in-place sorting
zbMATH Keywords: heapsort
zbMATH Keywords: quicksort
zbMATH Keywords: analysis of algorithms
author: Domenico Cantone
author: Gianluca Cincotti
describes a project that uses: LEDA
describes a project that uses: Find
describes a project that uses: Quicksort
MaRDI profile type: Publication
cites work: A variant of heapsort with almost optimal number of comparisons
cites work: An average case analysis of Floyd's algorithm to construct heaps
cites work: Q4728256
cites work: Q4692507
cites work: Q3945583
cites work: Q4953348
cites work: Q4057549
cites work: Building heaps fast
cites work: Q3998244
cites work: Implementing Quicksort programs
cites work: BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
cites work: The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than \(n \log n+1.1n\)
full work available at URL: s0304-3975(01)00288-2
OpenAlex ID: W2517692465
description: scientific article; zbMATH DE number 1776345