Chapter

 4 Sor4ng:  Heapsort  and  Quicksort

Data Structures and Algorithms

Chapter 4

Werner Nutt

Master Informatique Data Structures and Algorithms                                                                     1

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Acknowledgments
• The course follows the book “Introduction to Algorithms‘”,
by Cormen, Leiserson, Rivest and Stein, MIT Press
[CLRST]. Many examples displayed in these slides are
taken from their book.
• These slides are based on those developed by
Michael Böhlen for this course.
(See [Link]
• The slides also include a number of additions made by
Roberto Sebastiani and Kurt Ranalter when they taught
later editions of this course
(See [Link]

Master Informatique Data Structures and Algorithms                                                                     2

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

DSA, Chapter 4: Overview

●
About sorting algorithms

●
Heapsort
– complete binary trees
– heap data structure

• Quicksort
– a popular algorithm
– very fast on average

Master Informatique Data Structures and Algorithms                                                                     3

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

DSA, Chapter 4: Overview

●
About sorting algorithms

●
Heapsort
– Complete binary trees
– Heap data structure

• Quicksort
– a popular algorithm
– very fast on average

Master Informatique Data Structures and Algorithms                                                                     4

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Why Sorting?
• “When in doubt, sort” –
one of the principles of algorithm design.

• Sorting is used as a subroutine in many algorithms:

– Searching in databases:
we can do binary search on sorted data
– Element uniqueness, duplicate elimination
– A large number of computer graphics and
computational geometry problems

Master Informatique Data Structures and Algorithms                                                                     5

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Why Sorting?/2

• Sorting algorithms represent

different algorithm design techniques.

• The lower bound for sorting of Ω(n log n)

is used to prove lower bounds of other problems.

Master Informatique Data Structures and Algorithms                                                                     6

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Sorting Algorithms so Far

• Insertion sort, selection sort, bubble sort
– Worst-case running time Θ(n2)
– In-place

• Merge sort
– Worst-case running time Θ(n log n)
– Requires additional memory Θ(n)

Master Informatique Data Structures and Algorithms                                                                     7

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

DSA, Chapter 4: Overview

●
About sorting algorithms

●
Heapsort
– Complete binary trees
– Heap data structure

• Quicksort
– a popular algorithm
– very fast on average

Master Informatique Data Structures and Algorithms                                                                     8

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Selection Sort

SelectionSort(A[1..n]):
SelectionSort(A[1..n]):
for ii (*
for (* 11 to
to n-1
n-1
A:
A: Find
Find the
the smallest
smallest element
element among
among A[i..n]
A[i..n]
B:
B: Exchange
Exchange it it with
with A[i]
A[i]

• A takes Θ(n) and B takes Θ(1): Θ(n2) in total

• Idea for improvement: smart data structure to
– do A and B in Θ(1)
– spend O(log n) time per iteration to maintain the
data structure
– get a total running time of O(n log n)

Master Informatique Data Structures and Algorithms                                                                     9

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Binary Trees

• Each node may have a

left and right child
– The left child of 7 is 1 9
– The right child of 7 is 8
– 3 has no left child 3 7
– 6 has no children
• Each node has at most
one parent 6 1 8
– 1 is the parent of 4
• The root has no parent
– 9 is the root 4
• A leaf has no children
– 6, 4 and 8 are leafs

Master Informatique Data Structures and Algorithms                                                                     10

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Binary Trees/2

• The depth (or level) of a node

x is the length of the path from
9
the root to x
– The depth of 1 is 2
– The depth of 9 is 0 3 7
• The height of a node x is the
length of the longest path from
x to a leaf 6 1 8
– The height of 7 is 2
• The height of a tree is the
height of its root 4
– The height of the tree is 3

Master Informatique Data Structures and Algorithms                                                                     11

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Binary Trees/3

• The right subtree of a node x is

the tree rooted at 9
the right child of x
– The right subtree of 9 is the tree
3 7
shown in blue
• The left subtree of a node x is
the tree rooted at 6 1 8
the left child of x
– The left subtree of 9 is the tree
shown in red 4

Master Informatique Data Structures and Algorithms                                                                     12

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Complete Binary Trees

• A complete binary tree is a binary tree where
– all leaves have the same depth
– all internal (non-leaf) nodes have two children
• A nearly complete binary tree is a binary tree where
– the depth of two leaves differs by at most 1
– all leaves with the maximal depth are as far left as
possible

Master Informatique Data Structures and Algorithms                                                                     13

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heaps
• A binary tree is a binary heap iff
– it is a nearly complete binary tree
– each node is greater than or equal to all its children
• The properties of a binary heap allow
– an efficient storage as an array (because it is a nearly
complete binary tree)
– a fast sorting (because of the organization of the
values)

Master Informatique Data Structures and Algorithms                                                                     14

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heaps/2
3
1

Heap property 16
2 3

A[Parent(i)] ≥ A[i] 15 10
4 5 6 7

8 7 9 3
Parent(i) 8 9 10

return ⌊i/2⌋ 2 4 1

Left(i)
return 2i 1 2 3 4 5 6 7 8 9 10

16 15 10 8 7 9 3 2 4 1
Right(i) Level: 0 1 2 3
return 2i+1
Master Informatique Data Structures and Algorithms                                                                     15
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heaps/3
• Notice the implicit tree links in the array:
children of node i are 2i and 2i+1
• The heap data structure can be used to implement a fast
sorting algorithm.
• The basic elements are
– Heapify: reconstructs a heap after an element was
modified
– BuildHeap: constructs a heap from an array
– HeapSort: the sorting algorithm

Master Informatique Data Structures and Algorithms                                                                     16

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heapify
• Input: index i in array A, number n of elements
• Binary trees rooted at Left(i) and Right(i) are heaps
• A[i] might be smaller than its children, thus violating the
heap property.
• Heapify makes A a heap by moving A[i] down the heap
until the heap property is satisfied again.

Master Informatique Data Structures and Algorithms                                                                     17

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heapify Example

1
1

2
16 16
3
2 3
4 10
4 5 6 7 14 10
4 5 6 7
14 7 9 3
8 9 10
8 7 9 3
8 9 10
2 8 1
1 2 4 1
16
2 3
14 10 [Link] Heapify(A,2)
4 5 6 7 [Link] A[2] with A[4] and
4 7 9 3 recursively call Heapify(A,4)
8 9 10 [Link] A[4] with A[9] and
2 8 1 recursively call Heapify(A,9)
[Link] 9 has no children,
so we are done
Master Informatique Data Structures and Algorithms                                                                     18
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heapify Algorithm

Heapify(A,i,n)
Heapify(A,i,n)
ll :=
:= 2*i;
2*i; //
// ll :=
:= Left(i)
Left(i)
rr :=
:= 2*i+1;
2*i+1; //// rr :=
:= Right(i)
Right(i)
if
if ll <=
<= nn and
and A[l]
A[l] >> A[i]
A[i]
then
then maxpos
maxpos :=:= ll
else
else maxpos
maxpos :=:= ii
if
if rr <=
<= nn and
and A[r]
A[r] >> A[max]
A[max]
maxpos
maxpos :=:= rr
if
if max
max !=
!= ii
swap(A,i,maxpos)
swap(A,i,maxpos)
Heapify(A,maxpos,n)
Heapify(A,maxpos,n)

Master Informatique Data Structures and Algorithms                                                                     19

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heapify: Running Time

The running time of Heapify on a subtree of size n rooted at i

includes the time to
– determine relationship between elements: Θ(1)
– run Heapify on a subtree rooted at one of the children of i
• 2n/3 is the worst-case size of this subtree
(half filled bottom level)
• T(n) ≤ T(2n/3) + Θ(1) implies T(n) = O(log n)
– Alternatively
• Running time on a node of height h: O(h) = O(log n)

Master Informatique Data Structures and Algorithms                                                                     20

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap

• Convert an array A[1...n] into a heap

• Notice that the elements in the subarray
A[( ⌊n/2⌋ + 1)...n] are 1-element heaps to begin with

BuildHeap(A)
BuildHeap(A)
for
for ii := ⌊n/2
:= ⌊n /2⌋⌋ to
to 11 do
do
Heapify(A,
Heapify(A, i, i, n)
n)

Master Informatique Data Structures and Algorithms                                                                     21

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap/2

1 1

2
4 2
4
3 3
1 3 1 3
4 5 6 7 4 5 6 7

2 16 9 10 2 16 9 10
8 9 10 8 9 10

14 8 7 14 8 7

4 1 3 2 16 9 10 14 8 7 4 1 3 2 16 9 10 14 8 7

●
Heapify(A, 7, 10)
●
Heapify(A, 6, 10)
●
Heapify(A, 5, 10)

Master Informatique Data Structures and Algorithms                                                                     22

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap/3

1 1

2
4 2
4
3 3
1 3 1 3
4 5 6 7 4 5 6 7

2 16 9 10 14 16 9 10
8 9 10 8 9 10

14 8 7 2 8 7

4 1 3 2 16 9 10 14 8 7 4 1 3 14 16 9 10 2 8 7

●
Heapify(A, 4, 10)

Master Informatique Data Structures and Algorithms                                                                     23

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap/4

1 1

2
4 2
4
3 3
1 3 1 10
4 5 6 7 4 5 6 7

14 16 9 10 14 16 9 3
8 9 10 8 9 10

2 8 7 2 8 7

4 1 3 14 16 9 10 2 8 7 4 1 10 14 16 9 3 2 8 7

●
Heapify(A, 3, 10)

Master Informatique Data Structures and Algorithms                                                                     24

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap/5

1 1

2
4 2
4
3 3
1 3 16 10
4 5 6 7 4 5 6 7

14 16 9 10 14 7 9 3
8 9 10 8 9 10

2 8 7 2 8 1

4 1 10 14 16 9 3 2 8 7 4 16 10 14 7 9 3 2 8 1

●
Heapify(A, 2, 10)

Master Informatique Data Structures and Algorithms                                                                     25

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap/6

1 1

2
4 2
16
3 3
16 10 14 10
4 5 6 7 4 5 6 7

14 7 9 3 8 7 9 3
8 9 10 8 9 10

2 8 1 2 4 1

4 16 10 14 7 9 3 2 8 1 16 14 10 8 7 9 3 2 4 1

●
Heapify(A, 1, 10)

Master Informatique Data Structures and Algorithms                                                                     26

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap: Analysis

• Correctness: induction on i,
all trees rooted at m > i are heaps

• Running time: n calls to Heapify

= n O(log n) = O(n log n)

• Non-tight bound, but good enough for an

overall O(n log n) bound for Heapsort.

• Intuition for a tight bound:

– most of the time Heapify works on
less than n element heaps
Master Informatique Data Structures and Algorithms                                                                     27
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Building a Heap: Analysis/2

• Tight bound:
– An n element heap has height log n.
– The heap has n/2h+1 nodes of height h.
– Cost for one call of Heapify is O(h).
log n log n
n h
T (n) *. h &1 O(h) *O(n . h )
h *0 2 h *0 2
• Math: , ,
k ,
1/ x
x
. k
kx *
(1 ' x) 2
.
k *0 x
k
*. k (1 / x) *
k *0
k

(1 ' 1 / x) 2
k *0

log n
h 1/ 2
T (n) *O(n . h ) *O(n 2
) *O(n)
h *0 2 (1 ' 1 / 2)

Master Informatique Data Structures and Algorithms                                                                     28

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

HeapSort

Heapsort(A)
Heapsort(A)
BuildHeap(A)
BuildHeap(A) O(n)
O(n)
for
for ii :=
:= nn toto 22 do
do nntimes
times
swap(A,1,i)
swap(A,1,i) O(1)
O(1)
nn :=
:= nn -- 11 O(1)
O(1)
Heapify(A,
Heapify(A, 1, 1, n)
n) O(log
O(logn)
n)

The total running time of Heapsort is

O(n) + n * O(log n) = O(n log n)

Master Informatique Data Structures and Algorithms                                                                     29

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heapsort 16 14 10
14 10 8 10 8 9
8 7 9 3 4 7 9 3 4 7 1 3
2 4 1 2 1 16 2 14 16

9 8 7
8 3 7 3 4 3
4 7 1 2 4 2 1 9 1 2 8 9
10 14 16 10 14 16 10 14 16

4 3 2
2 3 2 1 1 3
1 7 8 9 4 7 8 9 4 7 8 9
10 14 16 10 14 16 10 14 16

1
2 3
4 7 8 9 1 2 3 4 7 8 9 10 14 16
10 14 16

Master Informatique Data Structures and Algorithms                                                                     30

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Heapsort: Summary
• Heapsort uses a heap data structure to improve
selection sort and make the running time asymptotically
optimal
• Running time is O(n log n) – like Merge Sort, but unlike
selection, insertion, or bubble sorts
• Sorts in place – like insertion, selection or bubble sorts,
but unlike merge sort
• The heap data structure is also used for other things
than sorting

Master Informatique Data Structures and Algorithms                                                                     31

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

DSA, Chapter 4: Overview

●
About sorting algorithms

●
Heapsort
– Complete binary trees
– Heap data structure

• Quicksort
– a popular algorithm
– very fast on average

Master Informatique Data Structures and Algorithms                                                                     32

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Quicksort
Characteristics
– Sorts in place
(like insertion sort, but unlike merge sort)
i.e., does not require an additional array
– Very practical, average sort performance O(n log n)
(with small constant factors), but worst case O(n2)

Master Informatique Data Structures and Algorithms                                                                     33

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Quicksort: The Principle

When applying the Divide&Conquer principle to sorting,
we obtain the following schema for an algorithm:
– Divide array segment A[l..r] into two subsegments,
say A[l..m] and A[m+1,r]
– Conquer: sort each subsegment by a recursive call
– Combine the sorted subsegments into a sorted
version of the original segment A[l..r]
Merge Sort takes an extreme approach in that
– no work is spent on the division
– a lot of work is spent on the combination
What does an algorithm look like where no work is spent
on the combination?
Master Informatique Data Structures and Algorithms                                                                     34
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Quicksort: The Principle/2

If no work is spent on the combination of the sorted
segments, then, after the recursive call,
– all elements in the left subsegment A[l..m] must be
≤ all elements in the right subsegment A[m+1..r]
However, the recursive call can only have sorted the
segments!

We conclude that the division must have partitioned A[l..r]

into
– a subsegment with small elements A[l..m]
– a subsegment with big elements A[m+1..r]

How can we write code for such a partition algorithm?

Master Informatique Data Structures and Algorithms                                                                     35

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Quicksort – the Principle

• To understand quick sort, let’s look at a high-level
description of the algorithm.
• A divide-and-conquer algorithm
– Divide: partition array into 2 subarrays such that
elements in the lower part
≤ elements in the higher part.
– Conquer: recursively sort the 2 subarrays
– Combine: trivial since sorting is done in place

Master Informatique Data Structures and Algorithms                                                                     36

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Quick Sort Algorithm: Overview

INPUT: A[1..n] – an array of integers
l,r – integers satisfying 1 ≤ l ≤ r ≤ n
OUTPUT: permutation of the segment A[l..r] s.t.
A[l]≤ A[l+1]≤ ...≤ A[r]

Quicksort(A,l,r)
if l < r then
m := Partition(A,l,r)
Quicksort(A,l,m-1)
Quicksort(A,m+1,r)

Partition divides the segment A[l..r] into

– a segment of “little elements” A[l..m-1]
– a segment of “big elements” A[m+1..r],
with A[m] in the middle between the two
Master Informatique Data Structures and Algorithms                                                                     37
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Partition
INPUT: A[1..n] – an array of integers
l,r – integers satisfying 1 ≤ l ) r ≤ n
OUTPUT: m – an integer with l ≤ m ≤ r
a permutation of A[l..r] such that
A[i]< A[m] for all i with l ≤ i ) m
A[m]≤ A[i] for all i with m ) i ≤ r

int Partition(A,l,r)
p := A[m]; // pivot, used for the split
ll := l-1; // last of the little ones
for bu := l to r-1 do
// bu is the beginning of the unknown area
if A[bu] < p
then swap(A,ll+1,bu); ll++;
// all elements < p are little ones
swap(A,ll+1,m)
// move the pivot into the middle position
Master Informatique Data Structures and Algorithms                                                                     38
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Partition: Loop Invariant

This version of partition has the following loop invariant
– A[i] < p, for all i with l ≤ i ≤ ll
(all little ones are < p)
– A[i] - p for all I with ll < i < bu
(all big ones are - p).
Clearly,
– this holds at the beginning of the execution
– this is maintained during the loop
– the loop terminates.
At the end of the loop, A[l..ll] comprises the little ones,
and A[ll+1..r-1] comprises the big ones.
Since p = A[r] is a big one, the postcondition holds after
the swap of A[ll+1] and A[p].
Master Informatique Data Structures and Algorithms                                                                     39
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Partitioning from the Endpoints

There is another approach to partitioning, due to Tony Hoare, the
inventor of Quicksort.
As before, we choose p:=A[r] as the pivot.
Then repeatedly,
– walk from right to left until you find an element + p
– walk from left to right until you find an element - p
– swap those elements.
Note that in this approach, we have no control where p ends up.
Therefore, Partition returns an index m such that
A[i] <= A[j], for all i, j with l + i + m and m+1 + j + r
Consequently, Quicksort(A,l,r) launches two recursive calls
Quicksort(A,l,m) and Quicksort(A,m+1,r)

Master Informatique Data Structures and Algorithms                                                                     40

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Partitioning from the Endpoints/2

6

i i j j
17 12 6 19 23 8 5 10
int Partition(A,l,r)
i j
01 p := A[r]
02 i := l-1 + p =10 + 10 12 6 19 23 8 5 17
03 j := r+1
04 while TRUE i j
05 repeat j := j-1
10 5 6 19 23 8 12 17
06 until A[j] + p
07 repeat i := i+1
08 until A[i] - p j i
09 if i<j 10 5 6 8 23 19 12 17
10 then swap(A,i,j)
11 else return i
10 5 6 8 23 19 12 17

Master Informatique Data Structures and Algorithms                                                                     41

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Quicksort with
Partitioning from the Endpoints

INPUT: A[1..n] – an array of integers

l,r – integers satisfying 1 ≤ l ≤ r ≤ n
OUTPUT: permutation of the segment A[l..r] s.t.
A[l]≤ A[l+1]≤ ...≤ A[r]

Quicksort(A,l,r)
if l < r then
m := Partition(A,l,r)
Quicksort(A,l,m)
Quicksort(A,m+1,r)

• Note the different parameters of the first recursive call!

Master Informatique Data Structures and Algorithms                                                                     42

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Master Informatique Data Structures and Algorithms                                                                     43

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Analysis of Quicksort
• Assume that all input elements are distinct
• The running time depends on the distribution of splits

Master Informatique Data Structures and Algorithms                                                                     44

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Best Case
• If we are lucky, Partition splits the array evenly:
T(n) = 2 T(n/2) + Θ(n)

n n
n/2 n/2 n
n/4 n/4 n/4 n/4 n
log n n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 n

Θ(n log n)

Master Informatique Data Structures and Algorithms                                                                     45

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Worst Case
• What is the worst case?
• One side of the partition has one element|
• T(n) = T(n-1) + T(1) + Θ(n)
= T(n-1) + 0 + Θ(n)
n
= . Θ( k )
k *1
n
= Θ%. k )
k *1

= Θ(n2)

Master Informatique Data Structures and Algorithms                                                                     46

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Worst Case/2

n n
1 n-1 n
1 n-2 n-1

n 1 n-3 n-2
1
2 3

1 1 2
2
Θ(n )

Master Informatique Data Structures and Algorithms                                                                     47

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Worst Case/3
• When does the worst case appear?
=> one of the partition segments is empty
– input is sorted
– input is reversely sorted

• Similar to the worst case of Insertion Sort

(reverse order, all elements have to be moved)

• But sorted input yields the best case for insertion sort

Master Informatique Data Structures and Algorithms                                                                     48

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Analysis of Quicksort
Suppose the split is 1/10 : 9/10

n n

(1/10)n (9/10)n n
10log n
(1/100)n (9/100)n (9/100)n (81/10)n n
10/9
log n

1 (81/1000)n (729/1000)n n

+n
1 +n

Θ(n log n)

Master Informatique Data Structures and Algorithms                                                                     49

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

An Average Case Scenario

Suppose, we alternate lucky L(n) = 2U(n/2) + Θ(n) lucky

and unlucky cases to get an U(n) = L(n-1) + Θ(n) unlucky
average behavior we consequently get
L(n) = 2(L(n/2 - 1) + Θ(n)) + Θ(n)
= 2L(n/2 - 1) + Θ(n)
= Θ(n log n)
n Θ(n)

1 n-1
n Θ(n)

(n-1)/2 (n-1)/2 n/2 n/2

Master Informatique Data Structures and Algorithms                                                                     50

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

An Average Case Scenario/2

• How can we make sure that we are usually lucky?
– Partition around the “middle” (n/2th) element?
– Partition around a random element
(works well in practice)
• Randomized algorithm
– running time is independent of the input ordering
– no specific input triggers worst-case behavior
– the worst-case is only determined by the output of the
random-number generator

Master Informatique Data Structures and Algorithms                                                                     51

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Randomized Quicksort
• Assume all elements are distinct
• Partition around a random element
• Consequently, all splits
1:n-1,
2:n-2,
...,
n-1:1
are equally likely with probability 1/n.

• Randomization is a general tool to improve algorithms

with bad worst-case but good average-case complexity.

Master Informatique Data Structures and Algorithms                                                                     52

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Randomized Quicksort/2

int RandomizedPartition(A,l,r)
i := Random(l,r)
exchange A[r] and A[i]
return Partition(A,l,r)

RandomizedQuicksort(A,l,r)
if l < r then
m := RandomizedPartition(A,l,r)
RandomizedQuicksort(A,l,m-1)
RandomizedQuicksort(A,m+1,r)

Master Informatique Data Structures and Algorithms                                                                     53

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Summary
• Heapsort
– same idea as Max sort, but heap data structure
helps to find the maximum quickly
– a heap is a nearly complete binary tree,
which here is implemented in an array
– worst case is n log n
• Quicksort
– partition-based: extreme case of D&C,
no work is spent on combining results
– popular, behind Unix ”sort” command
– very fast on average
– worst case performance is quadratic
Master Informatique Data Structures and Algorithms                                                                     54
 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Comparison of Sorting Algorithms

• Running time in ordered random inverse

seconds, n=2048
• Absolute values are Insertion 0.22 50.74 103.8
not important;
Selection 58.18 58.34 73.46
compare values with
each other Bubble 80.18 128.84 178.66
• Relate values to
asymptotic running Heap 2.32 2.22 2.12
time (n log n, n2) Quick 0.72 1.22 0.76

Master Informatique Data Structures and Algorithms                                                                     55

 Chapter  4 Sor4ng:  Heapsort  and  Quicksort

Next Chapter
• Dynamic data structures
– Pointers
– Lists, trees
• Abstract data types (ADTs)
– Definition of ADTs
– Common ADTs

Master Informatique Data Structures and Algorithms                                                                     56