4/26/2020

Analysis of Algorithm

Department of Computer Science &

Software Engineering
University of Swat

CS Course : Analysis of Algorithm

Course Instructor : Muzammil Khan

Chapter 4

Sorting Algorithms
(Elementary Sort Algorithms)

1
 4/26/2020

Other Resources
 Animated Sorting Examples
 http://www.ee.ryerson.ca/~courses/coe428/intro/introduction.html

Analysis of Algorithm

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 etc
 Sorting by Counting
 These depend on the characteristics of individual data items
 The sort method has limited application
 Examples include
 Radix Sort, Bucket Sort etc
Analysis of Algorithm

2
 4/26/2020

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

Insertion Sort

3
 4/26/2020

Insertion Sort
 The key is compared with the successive elements on the left
 Until a smaller element is found
 Key is inserted
 By shifting all the elements to right

Analysis of Algorithm

Insertion Sort
 Illustration

Analysis of Algorithm

4
 4/26/2020

Insertion Sort

Analysis of Algorithm

Insertion Sort Analysis

Cost Times
C1 1
C2 n
C3 n–1
C4 n–1


n
C5 tj
j 2


n
C6
j 2
(t j  1)

n
C7
j 2
(t j  1)
C8 n–1

T (n)  c1  c2 n  c3 (n  1)  c4 (n  1)  c5  t j  c6  t j  1  c7  t j  1  c8 (n  1)
n n n

j 2 j 2 j 2
Analysis of Algorithm

5
 4/26/2020

Insertion Sort (Best Case Scenario)

 The best case occur when
 The input is Presorted
 The key is written back
 After comparison
 That is,
 There is no moves / shifting to right of the elements

 Illustration
 Next slide

Analysis of Algorithm

Insertion Sort (Best Case Scenario) (Cont...)

 If A[2] is selected as Key
 One comparison is done
 If A[3] is selected as Key
 One comparison is done
 If A[4] is selected as Key
 One comparison is done
. And so on…
 If A[n] is selected as Key
 One comparison is done
 Thus, n-1 comparison are done
 Best case running of insertion sort
 θ (n-1) = θ (n)
Analysis of Algorithm

6
 4/26/2020

Insertion Sort (Worst Case Scenario)

 The worst case occur when
 The input is in reverse sorted
 The key is inserted in the left most position
 Maximum number of comparison
 That is,
 Maximum number of moves / shifting to right of the
elements involved

 Illustration
 Next slide

Analysis of Algorithm

Insertion Sort (Worst Case Scenario) (Cont...)

 If A[2] is selected as Key
 One comparison is done
 If A[3] is selected as Key
 Two comparison is done
 If A[4] is selected as Key
 Three comparison is done
. And so on…
 If A[n] is selected as Key
 n-1 comparison is done
Thus, Tw(n) = c[1+2+3+…+(n-2)+(n-1)]
= c. n(n-1)/2 = θ (n2)
 Worst case running of insertion sort
 θ (n2)
Analysis of Algorithm

7
 4/26/2020

Insertion Sort (Average Case Scenario)

 In order to find average case running time
 Consider the expected cost of inserting an element in
subarray of k elements
 Using probabilistic analysis

 Insertion sort procedure looks for

 The position of the element just smaller than the key
 The insertion of requisite element has equal probability of
being in any of the k locations
 That is 1 / k
Analysis of Algorithm

Insertion Sort (Average Case Scenario)

 Each insertion of key cause one shift to the right
 Assuming that c is the unit cost
 The following table summarizes
 The number of shift operation &
 Associated cost

Analysis of Algorithm

8
 4/26/2020

Insertion Sort (Average Case Scenario)

Analysis of Algorithm

Selection Sort

9
 4/26/2020

Selection Sort
 The main Idea
 Find the smallest element in the array
 Exchange it with the element in the first position
 Find the second smallest element and exchange it with the
element in the second position
 Continue until the array is sorted

 Disadvantage:
 Running time depends only slightly on the of order in the
file

Analysis of Algorithm

Selection Sort Illustration

 Find the smallest element in the
unsorted portion of array
 Interchange the smallest element with the one at the front of
the unsorted portion

 Find the smallest element in the

unsorted portion of array
 Interchange the smallest element with the one at the front of
the unsorted portion

Analysis of Algorithm

10
 4/26/2020

Selection Sort Illustration (Cont...)

 Find the smallest element in the
unsorted portion of array
 Interchange the smallest element with the one at the front of
the unsorted portion

 Repeat the above step until the

input is sorted

 n - 1 repetitions required
 Last element is automatically sorted
Analysis of Algorithm

Selection Sort Algorithm

Cost Times
C1 1
C2 n
C3 n–1

n 1
C4 j 1
( n  j  1)

n 1
C5 j 1
(n  j )

n 1
C6 j 1
( n  j)
C7 n–1

n 1 n 1 n 1
T (n)  c1  c2 n  c3 (n  1)  c4  (n  j  1)  c5   n  j   c6   n  j   c7 (n  1)  (n 2 )
j 1 j 1 j 2
Analysis of Algorithm

11
 4/26/2020

Selection Sort Algorithm

Analysis of Algorithm

Homework
 Analyze the
 The selection sort for all three cases

 Study the following Algorithms

 Bubble Sort
 External Sort
 Shell Sort
 Etc…

Analysis of Algorithm

12