6/11/2019

Analysis of Algorithm

Department of Computer Science &

Software Engineering
University of Swat

CS Course : Analysis of Algorithm

Course Instructor : Muzammil Khan

Chapter 6

Sorting Algorithms
(Advanced Sorting Algorithms)

1
 6/11/2019

Sorting Algorithms - Classification

 The sorting algorithms are classified into two categories
 On the basis of underlying procedure used

 Sorting by Comparison
 These are based on comparison of keys
 The method has general applicability
 Examples are selection sort, quick sort

 Sorting by Counting
 These depend on the characteristics of individual data items
 The sort method has limited application
 Examples include radix sort, bucket sort,
Analysis of Algorithm

Sorting by Comparison
 The Sorting by Comparison method sorts input
 By comparing pairs of keys in the input.
 Elementary Algorithms
 Are inefficient but easy to implement
 Their running times are θ(n2)
 Common algorithms are
 Insertion sort, Exchange sort, Selection sort
 Advanced Algorithms
 Advanced algorithms are efficient
 Implementations are usually based on recursive function calls
 Their running times are θ(n lg n)
 The typical advanced algorithms include
 Merge sort, Quick sort, Heap sort
Analysis of Algorithm

2
 6/11/2019

Sorting Algorithms
Algorithm Design Approach Sort in Place Complexity

Insertion Sort Incremental Yes (n2)

Selection Sort Incremental Yes (n2)

Bubble Sort Incremental Yes (n2)

Merge Sort Divide & Conquer No Let’s see !!

Analysis of Algorithm

Divide and Conquer Approach

 Divide the problem into a number of sub-problems
 D(n) - Time to divide a problem into sub-problems
 Conquer the sub-problems by solving them recursively
 aT(n/b) - Time to conquer each sub-problem
 If sub-problem sizes are small, they can be solved in a
straightforward manner
 Combine the solution of sub-problems into the solution for
the original problem
 C(n) – Time to combine sub-problems
 Total time
 T(n) = aT(n/b) + D(n) + C(n)
Analysis of Algorithm

3
 6/11/2019

Merge Sort

Merge Sort Idea

 To sort an array A[p ... r]
 Divide
 Divide the n-element sequence to be sorted into two
subsequences of n/2 elements each
 When the size of the sequences is 1 there is nothing more to do
 Conquer
 Sort the subsequences recursively using merge sort
 Starting from lower level to upper level (up-to whole solution)
 Combine
 Merge the two sorted subsequences
Analysis of Algorithm

4
 6/11/2019

Merge Sort - Illustration

Analysis of Algorithm

Merge Sort
1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

p q r
MERGE-SORT(A, p, r)
if p < r ►Check for base case
then q ← (p + r)/2 ►Divide
MERGE-SORT(A, p, q) ►Conquer 1st half (Recursively sort)
MERGE-SORT(A, q + 1, r) ►Conquer 2nd half (Recursively sort)
MERGE(A, p, q, r) ►Combine the 2 halves

 Initial call: MERGE-SORT(A, 1, n)

Analysis of Algorithm

5
 6/11/2019

1 2 3 4 5 6 7 8

Merge Sort Calls 5 7 3 8 2 6 1 4

Merge-Sort(A, 1, 8) Here p = 1, r = 8 & q = 4 as p < r

MS(A, 1, 4)
MS(A, 1, 2)
MS(A, 1, 1) ►5
MS(A, 2, 2) ►7
M(A, 1, 1, 2) ► 5, 7
MS(A, 3, 4)
MS(A, 3, 3) ►3
MS(A, 4, 4) ►8
M(A, 3, 3, 4) ► 3, 8
M(A, 1, 2, 4) ► 3, 5, 7, 8
MS(A, 5, 8) ► Next slide
Analysis of Algorithm

1 2 3 4 5 6 7 8

Merge Sort Calls (Cont...) 5 7 3 8 2 6 1 4

Merge-Sort(A, 1, 8)
MS(A, 5, 8)
MS(A, 5, 6)
MS(A, 5, 5) ►2
MS(A, 6, 6) ►6
M(A, 5, 5, 6) ► 2, 6
MS(A, 7, 8)
MS(A, 7, 7) ►1
MS(A, 8, 8) ►4
M(A, 7, 7, 8) ► 1, 4
M(A, 5, 6, 8) ► 1, 2, 4, 6
M(A, 1, 4, 8) ► 1, 2, 3, 4, 5, 6, 7, 8 ► Sorted
Analysis of Algorithm

6
 6/11/2019

Merge Sort (Cont...)

1 2 3 4 5 6 7 8
 Divide 5 2 q=4
4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

Analysis of Algorithm

Merge Sort (Cont...)

1 2 3 4 5 6 7 8
 Conquer & Merge 1 2 2 3 4 5 6 7

1 2 3 4 5 6 7 8

2 4 5 7 1 2 3 6

1 2 3 4 5 6 7 8

2 5 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6
Analysis of Algorithm

7
 6/11/2019

p q r
1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6
Merge Sort - Pseudocode
n1 n2

p q

L 2 4 5 7 
q +1 r

R 1 2 3 6 

Analysis of Algorithm

Merge Sort – Recurrence Relation

 Recall for Divide and Conquer algorithms
T(n) = aT(n/b) + D(n) + C(n)

 Here a=2, and if we assume n is a power of 2, then each

divide step leads to sub-arrays of size n/2

 D(n)=θ(1) ► division take constant time

 C(n)= θ(n) ► combining n elements

 T(n)=2T(n/2)+θ(n)
Analysis of Algorithm

8
 6/11/2019

Merge Sort – Worst-Case Scenario

Analysis of Algorithm

Merge Sort – Worst-Case Scenario

Solving by Substitution Method
As T(n) = 2T(n/2)+c.n ………… (1)
Solve for T(n/2), T(n/4), T(n/8) . . .
T(n/2) = 2 T(n/4)+c.n/2
Eq (1) => T(n) = 2(2T(n/4)+c.n/2)+c.n
= 4T(n/4)+ 2.c.n/2 + c.n
= 22 T(n/22)+2c.n ……….. (2)
Now T(n/4)
T(n/4) = 2T(n/8)+c.n/4
Eq (2) => T(n) = 22 (2T(n/8)+c.n/4)+2c.n
= 23 T(n/23)+4.c.n/4+2cn
= 23 T(n/23)+3c.n
Analysis of Algorithm

9
 6/11/2019

Merge Sort – Worst-Case Scenario

Solving by Substitution Method (Cont...)
Similarly
T(n) = 24 T (n/24) +4c.n
If n=2i Then
T(2i) = 2iT(2i/2i)+ i c.n
= 2iT(1)+ i c.n
As T(1) = Ɵ (1) = c
So T(2i) = 2ic + ic.n
As assumed
n= 2i
i=lg2n

Analysis of Algorithm

Merge Sort – Worst-Case Scenario

Solving by Substitution Method (Cont...)
So T(n) = nc+lg2n.c.n
= cn(1+lg2n)
= cnlgn+cn

 Ignoring low order Terms and constants

 T(n) = Ɵ(nlgn)

Analysis of Algorithm

10
 6/11/2019

Merge Sort
Worst, Average and Best-Case Scenario
 Worst case running time of merge sort is
 θ(nlgn)

 Average case running time of merge sort is also

 θ(nlgn)

 Best case ?

Analysis of Algorithm

Merge Sort (Cont...)

 Running time insensitive of the input

 Advantage
 Guaranteed to run in (nlgn)

 Disadvantage
 Requires extra space N

Analysis of Algorithm

11
 6/11/2019

Sort Challenge 1
 Problem
 Sort a file of huge records with tiny keys

 Example application: Reorganize your MP-3 files

 Which method to use?

A. Merge sort, guaranteed to run in time  nlgn
B. Selection sort
C. Bubble sort
D. Insertion sort
E. A custom algorithm for huge records/tiny keys
Analysis of Algorithm

Solution
 Insertion sort or bubble sort?
 NO, too many exchanges

 Selection sort?
 YES, it takes linear time for exchanges

 Merge sort or custom method?

 Probably not
 Selection sort simpler, does less swaps

Analysis of Algorithm

12
 6/11/2019

Sort Challenge 2
 Problem
 Sort a huge randomly-ordered file of small records

 Application: Process transaction record for a phone

company

 Which sorting method to use?

A. Bubble sort
B. Selection sort
C. Merge sort guaranteed to run in time  nlgn
D. Insertion sort
Analysis of Algorithm

Solution
 Selection sort?
 NO, always takes quadratic time
 Bubble sort?
 NO, quadratic time for randomly-ordered keys
 Insertion d?
 NO, quadratic time for randomly-ordered keys
 Merge sort?
 YES, it is designed for this problem
Analysis of Algorithm

13
 6/11/2019

Sort Challenge 3
 Problem
 Sort a file that is already almost in order
 Applications
 Re-sort a huge database after a few changes
 Double check that someone else sorted a file
 Which sorting method to use?
A. Merge sort, guaranteed to run in time  nlgn
B. Selection sort
C. Bubble sort
D. A custom algorithm for almost in-order files
E. Insertion sort
Analysis of Algorithm

Solution
 Selection sort?
 NO, always takes quadratic time
 Bubble sort?
 NO, bad for some definitions of “almost in order”
 Example:
 BCDEFGHIJKLMNOPQRSTUVWXYZA
 Insertion sort?
 YES, takes linear time for most definitions of “almost in
order”
 Merge sort or custom method?
 Probably not: insertion sort simpler and faster
Analysis of Algorithm

14
 6/11/2019

Quick Sort

Quick Sort
 Design Approach
 Divide and Conquer
 Procedure take place in two phases
 Given array
 Phase #1 (Divide)
 An array element is chosen as Pivot

 The array is partitioned into two sub-arrays (by pivot value)

 All elements on the left are less then pivot value and
 All elements on the right are greater or equal to pivot value

Analysis of Algorithm

15
 6/11/2019

Quick Sort (Cont...)

 Phase #2 (Conquer)
 The left and right sub-arrays are sorted recursively

Analysis of Algorithm

Quick Sort Pseudo code

QUICKSORT(A, p, r)
1. if p < r ►Check for base case
2. then q ← PARTITION(A, p, r) ►Create Partitions
3. QUICKSORT(A, p, q-1) ►Sort left side of the pivot
4. QUICKSORT(A, q+1, r) ►Sort right side of the pivot

Analysis of Algorithm

16
 6/11/2019

Quick Sort Pseudo code (Cont...)

PARTITION (A, p, r) Description
1. x ← A[r] ► Need to addddd description
2. i ← p-1
3. for j ← p to r-1
4. do if A[j] <= x
5. then i ← i+1
6. exchange A[i] ↔ A[j]
7. exchange A[i+1] ↔ A[r]
8. return i+1

Analysis of Algorithm

Analysis of Quick Sort

 Running time of Quick sort depends on
 Whether partition is balanced or unbalanced
 This in turn depends on elements (pivot) used for
partitioning

Analysis of Algorithm

17
 6/11/2019

Quick Sort – Best-Case Scenario

 In best case
 The array is partitioned into two nearly equal sub-array

 Recurrence relation for best case running time is

Analysis of Algorithm

Quick Sort – Best-Case Scenario (Cont...)

Analysis of Algorithm

18
 6/11/2019

Quick Sort – Worst-Case Scenario

 The worst case arises
 When the given array is in presorted
 The partitioned result in a single right partition
 The left partition is empty
 In this case
 The array is scanned from left to right until
 The pointer cross over

 As shown
 Next slide

Analysis of Algorithm

Quick Sort – Worst-Case Scenario (Cont...)

Analysis of Algorithm

19
 6/11/2019

Quick Sort – Worst-Case Scenario (Cont...)

 The worst case arises
 When the given array is in reverse sorted
 The partitioned result in a single left partition
 The right partition is empty
 In this case
 The array is scanned from left to right until
 The pointer cross over

 As shown
 Next slide

Analysis of Algorithm

Quick Sort – Worst-Case Scenario (Cont...)

Analysis of Algorithm

20
 6/11/2019

Quick Sort – Worst-Case Scenario (Cont...)

 Consider the case where left partition is empty

 The recurrence relation for worst case

 Since left partition is empty, recurrence simplifies to

 Same recurrence applies when right partition is empty

Analysis of Algorithm

Quick Sort – Worst-Case Scenario (Cont...)

 The recurrence

 Can be solved by iteration method

 Iteration yields the solution as

 The worst case running time of worst case is

 Θ(n2)
Analysis of Algorithm

21
 6/11/2019

Quick Sort – Average-Case Scenario

 In average case, we assume that
 The pivot can be any array element of size n
 By probabilistic analysis
 1/n is the probability of any array element to be pivot

 As shown
 Next slide

Analysis of Algorithm

Quick Sort – Average-Case Scenario (Cont...)

Analysis of Algorithm

22
 6/11/2019

Quick Sort – Average-Case Scenario (Cont...)

 By summing over running time for all probable locations of

pivot and associated cost
 The Recurrence

Analysis of Algorithm

Quick Sort – Average-Case Scenario (Cont...)

Analysis of Algorithm

23
 6/11/2019

Quick Sort – Average-Case Scenario (Cont...)

Analysis of Algorithm

Quick Sort – Average-Case Scenario (Cont...)

Analysis of Algorithm

24
 6/11/2019

Pivot Selection
 Pivot influence performance of quick sort algorithm
 There are four choices
 Left-most element
 The 1st element is chosen as pivot
 There is chance of bad partitioning

 Right-most element
 The last element is chosen as pivot
 There is chance of bad partitioning

Analysis of Algorithm

Pivot Selection
 Medium element
 The middle element is chosen as pivot

 Random element
 An element is selected randomly
 The random selection reduces/ minimize the chances of bad
partitioning

Analysis of Algorithm

25
 6/11/2019

Randomized Quick Sort

Analysis of Algorithm

Heap Sort

26
 6/11/2019

For MS
 Heap sort
 Count sort
 Radix sort
 Bucket sort

 Include in the lectures

Analysis of Algorithm

27