1 of 32

Insertion Sort, Selection Sort, Bubble Sort, Radix Sort

​

Compiled By

Prof. Dharmesh R. Tank

CE\IT Department, LDRP-ITR

Design and Analysis of Algorithm

�Unit 2: Analysis of Algorithms(II)

2 of 32

The Sorting Problem

  • Input:
    • A sequence of n numbers a1, a2, . . . , an
  • Output:
    • A permutation (reordering) a1’, a2’, . . . , an’ of the input sequence such that a1’ ≤ a2’ ≤ · · · ≤ an’

3 of 32

Structure of data

4 of 32

Why Study Sorting Algorithms?

  • There are a variety of situations that we can encounter
    • Do we have randomly ordered keys?
    • Are all keys distinct?
    • How large is the set of keys to be ordered?
    • Need guaranteed performance?

​

  • Various algorithms are better suited to some of these situations

5 of 32

Some Definitions

  • Internal Sort
    • The data to be sorted is all stored in the computer’s main memory.
  • External Sort
    • Some of the data to be sorted might be stored in some external, slower, device.
  • In Place Sort
    • The amount of extra space required to sort the data is constant with the input size.

6 of 32

Stability

  • A STABLE sort preserves relative order of records with equal keys

Sorted on first key:

Sort file on second key:

Records with key value 3 are not in order on first key!!

7 of 32

Insertion Sort

  • Idea: like sorting a hand of playing cards
    • Start with an empty left hand and the cards facing down on the table.
    • Remove one card at a time from the table, and insert it into the correct position in the left hand
      • compare it with each of the cards already in the hand, from right to left
    • The cards held in the left hand are sorted
      • these cards were originally the top cards of the pile on the table

8 of 32

Insertion Sort

To insert 12, we need to make room for it by moving first 36 and then 24.

6

10

24

12

36

9 of 32

Insertion Sort

6

10

24

36

12

10 of 32

Insertion Sort

6

10

24

36

12

11 of 32

Insertion Sort

6

10

24

36

12

12 of 32

Insertion Sort

5 2 4 6 1 3

Input Array

left sub-array

right sub-array

at each iteration, the array is divided in two sub-arrays:

sorted

unsorted

13 of 32

Insertion Sort

14 of 32

Insertion Sort

Alg.: INSERTION-SORT(A)

for j ← 2 to n

do key ← A[ j ]

Insert A[ j ] into the sorted sequence A[1 . . j -1]

i ← j - 1

while i > 0 and A[i] > key

do A[i + 1] ← A[i]

i ← i – 1

A[i + 1] ← key

  • Insertion sort – sorts the elements in place

a8

a7

a6

a5

a4

a3

a2

a1

1

2

3

4

5

6

7

8

key

15 of 32

Loop Invariant for Insertion Sort

​

Alg.: INSERTION-SORT(A)

for j ← 2 to n

do key ← A[ j ]

Insert A[ j ] into the sorted sequence A[1 . . j -1]

i ← j - 1

while i > 0 and A[i] > key

do A[i + 1] ← A[i]

i ← i – 1

A[i + 1] ← key

Invariant: at the start of the for loop the elements in A[1 . . j-1] are in sorted order

16 of 32

Analysis of Insertion Sort

cost times

c1 n

c2 n-1

0 n-1

c4 n-1

c5

c6

c7

c8 n-1

INSERTION-SORT(A)

for j ← 2 to n

do key ← A[ j ]

Insert A[ j ] into the sorted sequence A[1 . . j -1]

i ← j - 1

while i > 0 and A[i] > key

do A[i + 1] ← A[i]

i ← i – 1

A[i + 1] ← key

tj: # of times the while statement is executed at iteration j

17 of 32

Best Case Analysis

  • The array is already sorted
    • A[i] ≤ key upon the first time the while loop test is run (when i = j -1)
    • tj = 1
  • T(n) = c1n + c2(n -1) + c4(n -1) + c5(n -1) + c8(n-1) = (c1 + c2 + c4 + c5 + c8)n + (c2 + c4 + c5 + c8)

= an + b = Θ(n) or Ω(n)

“while i > 0 and A[i] > key”

18 of 32

Worst Case Analysis

  • The array is in reverse sorted order
    • Always A[i] > key in while loop test
    • Have to compare key with all elements to the left of the j-th position ⇒ compare with j-1 elements ⇒ tj = j

​

​

​

a quadratic function of n

​

  • T(n) = Θ(n2) order of growth in n2

“while i > 0 and A[i] > key”

using

we have:

19 of 32

Insertion Sort - Summary

  • Advantages
    • Good running time for “almost sorted” arrays Θ(n)
    • Best case Θ(n) or Ω(n) when array is sorted or single element in the list.
  • Disadvantages
    • Θ(n2) or O(n2) running time in worst and average case

20 of 32

Bubble Sort

  • Idea:
    • Repeatedly pass through the array
    • Swaps adjacent elements that are out of order

​

​

​

​

  • Easier to implement, but slower than Insertion sort

1

2

3

n

i

1

3

2

9

6

4

8

j

21 of 32

Example

1

3

2

9

6

4

8

i = 1

j

3

1

2

9

6

4

8

i = 1

j

3

2

1

9

6

4

8

i = 1

j

3

2

9

1

6

4

8

i = 1

j

3

2

9

6

1

4

8

i = 1

j

3

2

9

6

4

1

8

i = 1

j

3

2

9

6

4

8

1

i = 1

j

3

2

9

6

4

8

1

i = 2

j

3

9

6

4

8

2

1

i = 3

j

9

6

4

8

3

2

1

i = 4

j

9

6

8

4

3

2

1

i = 5

j

9

8

6

4

3

2

1

i = 6

j

9

8

6

4

3

2

1

i = 7

j

22 of 32

Bubble Sort

Alg.: BUBBLESORT(A)

for i ← 1 to length[A]

do for j ← length[A] downto i + 1

do if A[j] < A[j -1]

then exchange A[j] ↔ A[j-1]

1

3

2

9

6

4

8

i = 1

j

i

23 of 32

Thus, T(n) = Θ(n2)

Alg.: BUBBLESORT(A)

for i ← 1 to length[A]

do for j ← length[A] downto i + 1

do if A[j] < A[j -1]

then exchange A[j] ↔ A[j-1]

T(n) =

c1(n+1) +

c2

c3

c4

= Θ(n) +

(c2 + c2 + c4)

Analysis of Bubble Sort

cost

times

C1

(n+1)

C2

​

C3

​

C4

​

24 of 32

Best Case Analysis

  • The array is already sorted
    • A[i] ≤ key upon the first time the while loop test is run (when i = j -1)
    • tj = 1
  • T(n) = c1n + c2(n -1) + c4(n -1) + c5(n -1) + c8(n-1) = (c1 + c2 + c4 + c5 + c8)n + (c2 + c4 + c5 + c8)

= an + b = Θ(n) or Ω(n)

“while i > 0 and A[i] > key”

25 of 32

Worst Case Analysis

  • The array is in reverse sorted order
    • Always A[i] > key in while loop test
    • Have to compare key with all elements to the left of the j-th position ⇒ compare with j-1 elements ⇒ tj = j

​

​

​

a quadratic function of n

​

  • T(n) = Θ(n2) order of growth in n2

“while i > 0 and A[i] > key”

using

we have:

26 of 32

Bubble Sort - Summary

  • Advantages
    • Good running time for “almost sorted” arrays Θ(n)
    • Best case Θ(n) or Ω(n) when array is sorted or single element in the list.
    • For best case, starting with pass one, there is no exchange of data occur.
  • Disadvantages
    • Θ(n2) or O(n2) running time in worst and average case

27 of 32

Selection Sort

  • 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 amount of order in the file

28 of 32

Example

1

3

2

9

6

4

8

8

3

2

9

6

4

1

8

3

4

9

6

2

1

8

6

4

9

3

2

1

8

9

6

4

3

2

1

8

6

9

4

3

2

1

9

8

6

4

3

2

1

9

8

6

4

3

2

1

29 of 32

Selection Sort

Alg.: SELECTION-SORT(A)

n ← length[A]

for j ← 1 to n - 1

do smallest ← j

for i ← j + 1 to n

do if A[i] < A[smallest]

then smallest ← i

exchange A[j] ↔ A[smallest]

​

1

3

2

9

6

4

8

30 of 32

Analysis of Selection Sort

Alg.: SELECTION-SORT(A)

n ← length[A]

for j ← 1 to n - 1

do smallest ← j

for i ← j + 1 to n

do if A[i] < A[smallest]

then smallest ← i

exchange A[j] ↔ A[smallest]

cost times

c1 1

c2 n

c3 n-1

c4

c5

c6

c7 n-1

31 of 32

Worst Case Analysis

  • The array is in reverse sorted order
    • Always A[i] > key in while loop test
    • Have to compare key with all elements to the left of the j-th position ⇒ compare with j-1 elements ⇒ tj = j

​

​

​

a quadratic function of n

​

  • T(n) = Θ(n2) order of growth in n2

“while i > 0 and A[i] > key”

using

we have:

32 of 32

Selection Sort - Summary

  • Advantages
    • Good running time for “almost sorted” arrays Θ(n)
    • Best case Θ(n2) or Ω(n2) when array is sorted or single element in the list.
  • Disadvantages
    • Θ(n2) running time in worst and average case