A Basic Comparison of Heap-Sort and Quick-Sort Algorithms

Merciadri Luca

Luca.Merciadri@student.ulg.ac.be

Abstract. We summarize here the biggest differences between Heap-sort and Quick-sort algorithms,

two useful algorithms for array sorting.

Keywords: algorithms, sort, heap-sort, quick-sort.

1 Introduction

It is well known that, to learn the complexity (denoted by O) of an algorithm, it is important to find a

resource-costly operation. Here, we describe the complexity of the Heap-sort and Quick-sort algorithms,

evidently depending upon the time T. These are useful algorithms for array sorting.

2 Heap-Sort

The heap-sort algorithm is an in situ algorithm: it does not need supplementary memory to work.

2.1 How It Works

The idea is to look at the array to sort as it was a binary tree. The first element is the root, the second is

descending from the first element, . . .A binary tree is drawn at Figure 1.

The aim is to obtain a heap, thus a binary tree verifying the following properties:

1. The maximal difference between the two leaves is 1 (all the leaves are on the last, or on the penultimate

line);

2. The leaves having the maximum depth are “heaped” on the left;

3. Each node has a bigger (resp. lower) value than its of its two children, for an ascending (resp. descending)

sort.

2.2 Complexity

The complexity of the heap-sort algorithm, for sorting a N elements array, is O(_N · log2 N). The proof is

given at Subsection 3.2, p. 2 assuming _ is known.

Fig. 1. Example of a binary tree.

3 Quick-sort

The quick-sort algorithm is not an in situ algorithm: it does need supplementary memory to work. This

stack memory can vary between log2 N and N. This algorithm is generally the most used one. We shall see

after (see Subsection 3.3, p. I) why.

3.1 How It Works

The idea is to choose a pivot element, and to compare each element to this pivot element. If an element is

inferior or equal to the pivot element, this element is put on the left of the pivot element. If the element is

strictly superior to the pivot element, it is put on the right of the pivot element. This operation is called

partitioning, and is recursively called until all the elements are sorted.

3.2 Complexity

The complexity of the quick-sort algorithm, for sorting a N elements array, is not always O(_N · log2 N)

(assuming _ is known). In fact, it can vary between _N · log2 N and _N2 (assuming _ is known).

O(N · log2

N) The complexity of the quick-sort algorithm is essentially O(N · log2 N) when the array’s

elements are not almost all sorted (assuming the pivot element is the first one of the array). The complexity

is the same (close to a _

_ factor) for the heap-sort algorithm.

Proof. Let tq, N and th denote respectively the time for the quick-sort algorithm if the elements have not

already been sorted, the number of elements of the array, and the time for the heap-sort algorithm, whatever

the case. We then have, knowing that tq = th, and considering1 each rearrangement gives two subzones of

identical sizes:

tq = _N + 2tq

_

N

2

_

= _N + 2

_

_N

2

+ 2tq

_

N

4

__

= _N + _N + 4tq

_

N

4

_

= _N + _N + 4

_

_N

4

+ 2tq

_

N

8

__

...

= _N + _N + · · · + _N + 2xtq

_

N

2x

_

| {z }

=0

= _|N + _N{+z · · · + _N}

x times with x=log2(2x)=log2(N)

= _N log2(N),

where N = 2x. ut

1 In fact, each rearrangement gives N−1

2 -sized subzones, but we here want to find a magnitude, and we consider

N

2

_

N−1

2 .

O

􀀀

N2_

The complexity of the quick-sort algorithm is essentially O

􀀀

N2

_

when the array’s elements are

almost all sorted (assuming the pivot element is the first one of the array).

Proof. Let tq denote the time for the quick-sort algorithm if the elements have already been sorted. We

then have

tq =

NX−1

i=1

_ (N − i) | {z }

at the arrangement i

= _(N − 1) + _(N − 2) + · · · + _

= _

_

N2 − N

2

_

' _ · N2.

ut

Remark 1. For another pivot choice, there is an initial disposition of the array’s element which lands to the

unfavorable case.

3.3 Why Is It Quick, Then

One can ask why the quick-sort is the most used algorithm if its complexity has a minimum of N · log2 N,

which is the same as the quick-sort. In fact, when both algorithms have same complexity (_N · log2 N for

the quick-sort, and _N · log2 N for the heap-sort), the quick-sort is faster because he has a proportionnality

coefficient which equals the half of the heap-sort’s proportionnality coefficient; mathematically, we have

_ =

_

2

.

4 Which One to Choose

There is no “ideal” solution about arrays’ sorting. If you want to predict precisely when your algorithm will

have finished, it is better to use the heap-sort algorithm, because the complexity of this one is always the

same. It is also the case if you know in advance that your array is almost sorted.

References

1. de Marneffe, Pierre-Arnoul: Introduction `a l’algorithmique (1998) ULg.

2. Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford: Introduction to Algo-

rithms. McGraw-Hill Book Company (2001)