Browse Prior Art Database

WORST CASE ANALYSIS OF HEAPSORT

IP.com Disclosure Number: IPCOM000128176D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 33K

Publishing Venue

Software Patent Institute

Related People

CLYDE P. KRUSKAL: AUTHOR [+4]

Abstract

An exact solution is given for the maximum number of comparisons required by heapsort, assuming that the number. of elements to be sorted is one less than a power of two. In addition, an algorithm is presented which produces data yielding the maximum number of comparisons.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

WORST CASE ANALYSIS OF HEAPSORT

CLYDE P. KRUSKAL

ELIA WEIXELBAUM

NOVEMBER 1979

REPORT N0. 018 a

* Submitted May 1977, revised November 1979.

This material is based upon work supported by the Department of Energy under Contract No. DE-AC02-76ER03077.

ABSTRACT

An exact solution is given for the maximum number of comparisons required by heapsort, assuming that the number. of elements to be sorted is one less than a power of two. In addition, an algorithm is presented which produces data yielding the maximum number of comparisons.

ACKNOWLEDGEMENTS:

We thank Robert Dewar for suggesting the problem and also for supplying helpful comments and encouragement. In addition, we thank Sal Stolfo and Martin Golumbic for reading an early draft and especially Allan Gottlieb for his careful perusal of umpteen different drafts. Finally, we thank Lucy Jones for her expert typing of this manuscript.

We thank Robert Dewar for suggesting the problem and also for supplying helpful comments and encouragement. In addition, we thank Sal Stolfo and Martin Golumbic for reading an early draft and especially Allan Gottlieb for his careful perusal of umpteen different drafts. Finally, we thank Lucy Jones for her expert typing of this manuscript.

INTRODUCTION

It is interesting to compare various sorting algorithms based on numbers of comparisons and exchanges. This point is emphasized in Knuth [Kn, sec. 5.3.1]: "... a theoretical study of this subject [counting comparisons] gives us a good deal of useful insight into the nature of sorting processes ..."

The most commonly known 0(n log n) comparison-exchange sorting algorithm not needing external storage is heapsort (sometimes referred to as treesort) [F1], [WiJ. It is relatively easy to calculate the maximum number of exchanges required by heapsort; in this paper, we calculate the maximum number of (key) comparisons required, assuming that the size of the input is one

New York University Page 1 Dec 31, 1979

Page 2 of 10

WORST CASE ANALYSIS OF HEAPSORT

less than a power of two. In addition, we exhibit an algorithm producing input yielding the maximum number of comparisons.

HEAPSORT ALGORITHM:

DEFINITION: A heap is a binary tree such that the root contains the largest value of the tree, and its sons (if it has sons) are the roots of subtrees that are also heaps.

As usual in heapsort, we view the array, Allen) as a tree. The left and right sons of A(i) are A(2i) and A(2i + 1) respectively. There are two phases to heapsort, CREATE HEAP and SELECT. CREATE HEAP, as the name indicates, forms a heap from the tree stored in the array, A. SELECT exchanges the root of the tree (which contains the largest value) with the last position of the tree, deletes that last position from the tree, and restores the remainder of the tree into a heap. This procedure is repeated until the root is the only remaining node in the tree. When completed, this results in the arra...