Algorithm design problem set

LE/EECS3101

Design and Analysis of Algorithms

Sorting Algorithms

Karim Jahed

Why Sorting?

• A large number of problems depends on a sorted input
• Efficiently searching a database using, for e.g., Binary Search.
• Computer graphics and computation geometry problems such as

closest pairs and unique elements.

• A very large number of sorting algorithms are developed using
different algorithm design technique.

• A lower bound on comparison-based sorting is Ω(n log n). This is
often useful in proving lower bounds for other problems.

1

Properties of sorting algorithms

• Worst-case running time.

• In-place?
• Does the algorithm require any auxiliary data structure?

• Stable?
• Does the algorithm maintains the relative order of equal elements?

2

Sorting algorithms – Recap

• Insertion Sort
• Worst case: O(n2)
• In-place
• Stable

• Selection Sort
• Worst case: O(n2)
• In-place
• Unstable

• Merge Sort
• Worst case: O(n log n)
• Not in-place
• Stable

3

Selection Sort – A possible improvement?

• Selection Sort
1. for i = n to 2

1.1 Find the largest element in A[1..i]

1.2 Exchange it with A[i]

• Finding n-1 largest elements takes up the bulk of the computation
time.

• Can we do better?

• Idea: use a data structure to do 1.1 in O(log n).

4

Selection Sort – A possible improvement?

• Selection Sort
1. for i = n to 2

1.1 Find the largest element in A[1..i]

1.2 Exchange it with A[i]

• Finding n-1 largest elements takes up the bulk of the computation
time.

• Can we do better?

• Idea: use a data structure to do 1.1 in O(log n).

4

Selection Sort – A possible improvement?

• Selection Sort
1. for i = n to 2

1.1 Find the largest element in A[1..i]

1.2 Exchange it with A[i]

• Finding n-1 largest elements takes up the bulk of the computation
time.

• Can we do better?
• Idea: use a data structure to do 1.1 in O(log n).

4

Max Heaps

A Max Heap is a binary tree that guarantees that the largest element is

always at the root of the tree. Looking up the maximum thus takes

constant time.

5

Max Heap – Insertion (1)

Suppose we want to insert the element k = 18 into the heap. First,

‘append’ k to the tree, then keep on swapping the k with its parent until

k ≤ its parent.

6

Max Heap – Insertion (1)

Suppose we want to insert the element k = 18 into the heap. First,

‘append’ k to the tree, then keep on swapping the k with its parent until

k ≤ its parent.

6

Max Heap – Insertion (1)

Suppose we want to insert the element k = 18 into the heap. First,

‘append’ k to the tree, then keep on swapping the k with its parent until

k ≤ its parent.

6

Max Heap – Insertion (1)

Suppose we want to insert the element k = 18 into the heap. First,

‘append’ k to the tree, then keep on swapping the k with its parent until

k ≤ its parent.

6

Max Heap – Max Element Extraction

Suppose we want to extract the maximum element (i.e., the root). First,

swap the root element with the element at the last leaf of the tree and

delete the leaf. Since the heap property is violated, we need to ‘heapify’

the tree. Similar to insertion, keep swapping the root with its largest

child.

7

Max Heap – Max Element Extraction

Suppose we want to extract the maximum element (i.e., the root). First,

swap the root element with the element at the last leaf of the tree and

delete the leaf. Since the heap property is violated, we need to ‘heapify’

the tree. Similar to insertion, keep swapping the root with its largest

child.

7

Max Heap – Max Element Extraction

Suppose we want to extract the maximum element (i.e., the root). First,

swap the root element with the element at the last leaf of the tree and

delete the leaf. Since the heap property is violated, we need to ‘heapify’

the tree. Similar to insertion, keep swapping the root with its largest

child.

7

Max Heap – Max Element Extraction

Suppose we want to extract the maximum element (i.e., the root). First,

swap the root element with the element at the last leaf of the tree and

delete the leaf. Since the heap property is violated, we need to ‘heapify’

the tree. Similar to insertion, keep swapping the root with its largest

child.

7

Max Heap – Max Element Extraction

We can represent a binary tree with n nodes using an array of n elements.

• Parent index: i/2
• Left child index: 2i
• Right child index 2i + 1 8

Max Heap – Heapify

1 precond left and right subtrees of i are heaps.

2 fun h e a p i f y ( A , n , i ) :

3 l = 2 i # l e f t c h i l d i n d e x

4 r = 2 i + 1 # r i g h t c h i l d i n d e x

5 l a r g e s t = i # a s s u m e p a r e n t i s l a r g e s t

6

7 i f l <= n and A [ l ] > A [ l a r g e s t ] :

8 l a r g e s t = l

9 i f r <= n and A [ r ] > A [ l a r g e s t ] :

10 l a r g e s t = r

11 i f l a r g e s t != i

12 swap ( A [ i ] , A [ l a r g e s t ] )

13 h e a p i f y ( A , n , l a r g e s t )

14 postcond subtree rooted at i is a heap

9

Max Heap – Heapify

1 precond left and right subtrees of i are heaps.

2 fun h e a p i f y ( A , n , i ) :

3 l = 2 i # l e f t c h i l d i n d e x

4 r = 2 i + 1 # r i g h t c h i l d i n d e x

5 l a r g e s t = i # a s s u m e p a r e n t i s l a r g e s t

6

7 i f l <= n and A [ l ] > A [ l a r g e s t ] :

8 l a r g e s t = l

9 i f r <= n and A [ r ] > A [ l a r g e s t ] :

10 l a r g e s t = r

11 i f l a r g e s t != i

12 swap ( A [ i ] , A [ l a r g e s t ] )

13 h e a p i f y ( A , n , l a r g e s t )

14 postcond subtree rooted at i is a heap

• What is the running time of heapify?

9

Max Heap – Heapify

1 precond left and right subtrees of i are heaps.

2 fun h e a p i f y ( A , n , i ) :

3 l = 2 i # l e f t c h i l d i n d e x

4 r = 2 i + 1 # r i g h t c h i l d i n d e x

5 l a r g e s t = i # a s s u m e p a r e n t i s l a r g e s t

6

7 i f l <= n and A [ l ] > A [ l a r g e s t ] :

8 l a r g e s t = l

9 i f r <= n and A [ r ] > A [ l a r g e s t ] :

10 l a r g e s t = r

11 i f l a r g e s t != i

12 swap ( A [ i ] , A [ l a r g e s t ] )

13 h e a p i f y ( A , n , l a r g e s t )

14 postcond subtree rooted at i is a heap

• What is the running time of heapify?
• In the worst case, heapify is invoked one time per level. Since the

height of the tree log n, the running time is in O(log n)
9

Heapify – Correctness

We can prove the correctness of heapify by induction over the height of

the tree h. P(h) = heapify correctly heapifies a tree of height h, i.e.,

the value at a parent node is greater than or equal to the values at its

children.

• Base case: For h = 1, the subtree contains only one node. A
one-node tree is a max heap. P(1) is true.

• Induction hypothesis: Assume P(h − 1) is true.
• Inductive step: We will prove P(h) is true. After line 10, largest

contains the index of the largest element between the parent and

both of its children. If the parent is smaller than at least one of its

children, line 12 swaps the parent with its largest child. After line

12, one of the subtrees (rooted at either the left or right child) is

unaffected and is already a heap. By the induction hypothesis, line

13 heapifies the other tree (of height h-1). Therefore, P(h) is true.

10

Building a Heap

Given an array A[1..n] we can convert it to a heap by heapifying each

subtree.

1 fun b u i l d H e a p ( A , n ) :

2 for i = n /2 downto 1

3 h e a p i f y ( A , n , i )

• Note that the leaf nodes (i > n/2) are heaps since each one of them
is a tree of height 1.

• heapify is called less than n times so the running time is in
O(n log n)

11

Building a Heap – A tighter bound

• O(n log n) is good enough for most cases but we can get a tighter
bound. Notice how heapify is invoked on much smaller subtrees

each time.

• heapify takes different time for each element i in A
• O(h) where h is the height of the subtree rooted at i.

• By counting the number of subtrees of height h, we can prove that
buildHeap is in O(n).

12

Heap Sort

1 fun h e a p S o r t (A [ 1 . . n ] ) :

2 b u i l d H e a p ( A)

3 precond A is a max heap

4 for i = n downto 2 :

5 i n v a r i a n t A[i+1..n] contains the n-i largest elements of

6 A in sorted order, and A[1..i] is a max heap

7 containing the remaining elements

8 swap ( A [ 1 ] , A [ i ] )

9 h e a p i f y ( A , i −1 , 1 )
10 postcond A is a sorted

13

Heap Sort – Correctness

LI: A[i+1..n] contains the n-i largest elements of A in sorted order, and

A[1..i] is a max heap containing the remaining elements.

• Initialization: In the first iteration A[i+1..n] (A[n+1..n]) is empty
(n+1 > n) and A is a max heap by the precondition. LI(1) holds.

• Maintenance: Assume L(i) is true. We will prove that L(i) =⇒
L(i-1). In the ith-iteration, the maximum element (A[1]) is

exchanged with the last element of the heap (A[i]) and the heap size

is shortened by 1. Therefore, before the ith-1 iteration, A[(i-1)+1..n]

contains the n-(i-1)=n-i+1 largest elements of A in sorted order.

Moreover, after the call to heapify, A[1..i-1] is a max heap. L(i-1)

holds.

• Termination: The loop terminates when i = 1. Per the loop
invariant, A[2..n] contains the n-1 largest elements of A in sorted

order. The remaining element at A[1] is therefore the minimum.

The array is sorted and the postcondition is asserted.

14

Heap Sort – Summary

• Heap Sort uses a heap data structure to improve selection sort and
make the running time asymptotically optimal.

• The worst case running time is in O(n log n).
• Heap Sort is in-place but, like selection sort, heap sort is unstable.

15

Quick Sort

1 fun q u i c k S o r t ( A [ 1 . . n ] , l , h ) :

2 i f l >= h :

3 return

4

5 p i v o t = p a r t i t i o n ( A , l , h )

6 q u i c k S o r t ( A , l , p i v o t )

7 q u i c k S o r t ( A , p i v o t + 1 , h )

Quick Sort is an in-place divide and conquer sorting algorithm.

• Divide: Partition the array into 2 subarrays such that elements in
the first part ≤ elements in the second part.

• Conquer: Recursively sort the 2 subarrays.

• Combine: Trivial since sorting is done in place.

16

Quick Sort – Partitioning

One way to partition the array is to take last element as pivot, place the

pivot element at its correct sorted position, then place all elements

smaller than the pivot to its left and all elements greater than the pivot

to its right.

1 fun p a r t i t i o n ( A [ 1 . . n ] , l , h ) :

2 p i v o t = A [ h ] # p i v o t i s r i g h t m o s t e l e m e n t

3 i = l − 1 # k e e p t r a c k o f t h e i n d e x
4 # o f t h e s m a l l e r e l e m e n t

5

6 for j = l o w to h i g h − 1 :
7 i f A [ j ] < p i v o t 8 i++ 9 swap (A [ i ] , A [ j ] ) 10 swap (A [ i + 1 ] , A [ h ] ) 11 return i + 1 17 Quick Sort - Running time The recurrence relation for quickSort is T (n) = T (k) + T (n −k − 1) + n Where k is the number of elements smaller than the pivot. • Worst case: pivot is smaller or larger than all the elements. T (n) = T (0) + T (n − 1) + n T (n) ∈ Θ(n2) • Best case: pivot is the middle element T (n) = 2T (n/2) + n T (n) ∈ Θ(n log n) • In practice, picking a random element as the pivot works well. 18 Quick Sort - Running time The recurrence relation for quickSort is T (n) = T (k) + T (n −k − 1) + n Where k is the number of elements smaller than the pivot. • Worst case: pivot is smaller or larger than all the elements. T (n) = T (0) + T (n − 1) + n T (n) ∈ Θ(n2) • Best case: pivot is the middle element T (n) = 2T (n/2) + n T (n) ∈ Θ(n log n) • In practice, picking a random element as the pivot works well. 18 Quick Sort - Running time The recurrence relation for quickSort is T (n) = T (k) + T (n −k − 1) + n Where k is the number of elements smaller than the pivot. • Worst case: pivot is smaller or larger than all the elements. T (n) = T (0) + T (n − 1) + n T (n) ∈ Θ(n2) • Best case: pivot is the middle element T (n) = 2T (n/2) + n T (n) ∈ Θ(n log n) • In practice, picking a random element as the pivot works well. 18 Quick Sort - Running time The recurrence relation for quickSort is T (n) = T (k) + T (n −k − 1) + n Where k is the number of elements smaller than the pivot. • Worst case: pivot is smaller or larger than all the elements. T (n) = T (0) + T (n − 1) + n T (n) ∈ Θ(n2) • Best case: pivot is the middle element T (n) = 2T (n/2) + n T (n) ∈ Θ(n log n) • In practice, picking a random element as the pivot works well. 18