IT202 – DS - Unit 1

Sorting and Searching

1
 Sorting – Definition
Definition:
Arranging a set of members either in ascending or descending order.
If ‘A’ is an array of ‘N’ elements, then they are arranged in sorted order
(ascending order) such that A[0] < A[1] < A[2] < …. < A[N].
Example :
Array before sorting : A[5] = {34, 78, 22, 17, 90}
Array after sorting in ascending order: A[5] = {17, 22, 34, 78, 90}
Array after sorting in descending order: A[5] = {90,78, 34,22,17}
Classification of Sorting Techniques
 1.1 BUBBLE SORT
❑In this sorting method, consecutive adjacent pairs of elements in
the array are compared and interchanged if they are not in order.
❑It takes (N-1) passes / iterations to sort the entire array.
❑In each pass,
❑The next largest element of the array sinks to its final position
❑Other small elements float or bubble up in the partially sorted list, hence the name
Bubble sort.
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}

Array A ↓

A[1] 16
A[2] 36
A[3] 4
A[4] 22
A[5] 100
A[6] 1
A[7] 54
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}
Iteration 1 – pair 1 compared – no swap required

Iteration 1
Array A ↓
Pair 1
A[1] 16 16
A[2] 36 36
A[3] 4 4
A[4] 22 22
A[5] 100 100
A[6] 1 1
A[7] 54 54
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}
Iteration 1 – pair 2 compared –swapping done

Iteration 1
Array A ↓
Pair 1 Pair 2
A[1] 16 16 16
A[2] 36 36 36
A[3] 4 4 4
A[4] 22 22 22
A[5] 100 100 100
A[6] 1 1 1
A[7] 54 54 54
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}
Iteration 1 – pair 3 compared – swapping done

Iteration 1
Array A ↓
Pair 1 Pair 2 Pair 3
A[1] 16 16 16 16
A[2] 36 36 36 4
A[3] 4 4 4 36
A[4] 22 22 22 22
A[5] 100 100 100 100
A[6] 1 1 1 1
A[7] 54 54 54 54
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}
Iteration 1 – pair 4 compared – no swap required

Iteration 1
Array A ↓
Pair 1 Pair 2 Pair 3 Pair 4
A[1] 16 16 16 16 16
A[2] 36 36 36 4 4
A[3] 4 4 4 36 22
A[4] 22 22 22 22 36
A[5] 100 100 100 100 100
A[6] 1 1 1 1 1
A[7] 54 54 54 54 54
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}
Iteration 1 – pair 5 compared – swapping done

Iteration 1
Array A ↓
Pair 1 Pair 2 Pair 3 Pair 4 Pair 5
A[1] 16 16 16 16 16 16
A[2] 36 36 36 4 4 4
A[3] 4 4 4 36 22 22
A[4] 22 22 22 22 36 36
A[5] 100 100 100 100 100 100
A[6] 1 1 1 1 1 1
A[7] 54 54 54 54 54 54
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}
Iteration 1 – pair 6 compared – swapping done

Iteration 1
Array A ↓
Pair 1 Pair 2 Pair 3 Pair 4 Pair 5 Pair 6
A[1] 16 16 16 16 16 16 16
A[2] 36 36 36 4 4 4 4
A[3] 4 4 4 36 22 22 22
A[4] 22 22 22 22 36 36 36
A[5] 100 100 100 100 100 100 1
A[6] 1 1 1 1 1 1 100
A[7] 54 54 54 54 54 54 54
 Exercise 1.1
Sort the following numbers using Bubble Sort
A[7] = {16, 36, 4, 22, 100, 1, 54}
At the end of iteration 1 the largest of all elements is placed in last position

Iteration 1 Iteration
Array A ↓ 1 result
Pair 1 Pair 2 Pair 3 Pair 4 Pair 5 Pair 6
A[1] 16 16 16 16 16 16 16 16
A[2] 36 36 36 4 4 4 4 4
A[3] 4 4 4 36 22 22 22 22
A[4] 22 22 22 22 36 36 36 36
A[5] 100 100 100 100 100 100 1 1
A[6] 1 1 1 1 1 1 100 54
A[7] 54 54 54 54 54 54 54 100
Exercise 1.1
Sort the following numbers using Bubble Sort
16, 36, 4, 22, 100, 1, 54
At the end of pass 2 / iteration 2 - the 2nd largest element is placed in the last but one position

Iterations →
Pass 1 Pass 2
Array A ↓
A[1] 16 16 4
A[2] 36 4 16
A[3] 4 22 22
A[4] 22 36 1
A[5] 100 1 36
A[6] 1 54 54
A[7] 54 100 100
Exercise 1.1
Sort the following numbers using Bubble Sort
16, 36, 4, 22, 100, 1, 54
Iteration 3 brings third largest member to its final place

Iterations →
Pass 1 Pass 2 Pass 3
Array A ↓
A[1] 16 16 4 4
A[2] 36 4 16 16
A[3] 4 22 22 1
A[4] 22 36 1 22
A[5] 100 1 36 36
A[6] 1 54 54 54
A[7] 54 100 100 100
Exercise 1.1
Sort the following numbers using Bubble Sort
16, 36, 4, 22, 100, 1, 54
At the end of pass 4 / iteration 4 - the 4th largest element is placed in its final position

Iterations →
Pass 1 Pass 2 Pass 3 Pass 4
Array A ↓
A[1] 16 16 4 4 4
A[2] 36 4 16 16 1
A[3] 4 22 22 1 16
A[4] 22 36 1 22 22
A[5] 100 1 36 36 36
A[6] 1 54 54 54 54
A[7] 54 100 100 100 100
Exercise 1.1
Sort the following numbers using Bubble Sort
16, 36, 4, 22, 100, 1, 54
Iteration 5 brings 5th largest member to its final place

Iterations →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5
Array A ↓
A[1] 16 16 4 4 4 1
A[2] 36 4 16 16 1 4
A[3] 4 22 22 1 16 16
A[4] 22 36 1 22 22 22
A[5] 100 1 36 36 36 36
A[6] 1 54 54 54 54 54
A[7] 54 100 100 100 100 100
Exercise 1.1
Sort the following numbers using Bubble Sort
16, 36, 4, 22, 100, 1, 54 – sorting completes at (n-1) / 6th pass

Iterations →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6
Array A ↓
A[1] 16 16 4 4 4 1 1
A[2] 36 4 16 16 1 4 4
A[3] 4 22 22 1 16 16 16
A[4] 22 36 1 22 22 22 22
A[5] 100 1 36 36 36 36 36
A[6] 1 54 54 54 54 54 54
A[7] 54 100 100 100 100 100 100
 Algorithm for Bubble Sort

Uses 2 nested iterations

– outer iteration repeated for n-1 of times for n-1 larger members
- Inner iteration gets the neighbouring pairs to compare and applies swap if needed
Bubble sort
Note:
1. The time complexity of bubble sort algorithm is O(𝑁 2 ).
N – No. of members in the array

2. The bubble sort algorithm logic is simple to implement but

number of comparisons and exchanges are more
 1.2 INSERTION SORT
❑It is based on the principle of insertion of data iteratively
❑On each iteration a new data is inserted at its ordered position in
an already sorted sub array
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Iteration 1 – 2nd member inserted – upto 2nd position array is sorted

Passes →
Pass 1
Array A ↓
A[1] 39 9
A[2] 9 39
A[3] 45
A[4] 63
A[5] 18
A[6] 81
A[7] 108
A[8] 54
A[9] 72
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Iteration 2 – 3rd member inserted – upto 3rd position array members are sorted

Passes →
Pass 1 Pass 2
Array A ↓
A[1] 39 9 9
A[2] 9 39 39
A[3] 45 45
A[4] 63
A[5] 18
A[6] 81
A[7] 108
A[8] 54
A[9] 72
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Iteration 3 – 4th member inserted – upto 4th position array members are sorted

Passes →
Pass 1 Pass 2 Pass 3
Array A ↓
A[1] 39 9 9 9
A[2] 9 39 39 39
A[3] 45 45 45
A[4] 63 63
A[5] 18
A[6] 81
A[7] 108
A[8] 54
A[9] 72
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Iteration 4 – 5th member inserted – upto 5th position array members are sorted

Passes →
Pass 1 Pass 2 Pass 3 Pass 4
Array A ↓
A[1] 39 9 9 9 9
A[2] 9 39 39 39 18
A[3] 45 45 45 39
A[4] 63 63 45
A[5] 18 63
A[6] 81
A[7] 108
A[8] 54
A[9] 72
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Pass 5 – 6th member inserted – upto 6th position array members are sorted

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5
Array A ↓
A[1] 39 9 9 9 9 9
A[2] 9 39 39 39 18 18
A[3] 45 45 45 39 39
A[4] 63 63 45 45
A[5] 18 63 63
A[6] 81 81
A[7] 108
A[8] 54
A[9] 72
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Pass 6 – 7th member inserted – upto 7th position array members are sorted

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6
Array A ↓
A[1] 39 9 9 9 9 9 9
A[2] 9 39 39 39 18 18 18
A[3] 45 45 45 39 39 39
A[4] 63 63 45 45 45
A[5] 18 63 63 63
A[6] 81 81 81
A[7] 108 108
A[8] 54
A[9] 72
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Pass 7 – 8th member inserted – upto 8th position array members are sorted

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7
Array A ↓
A[1] 39 9 9 9 9 9 9 9
A[2] 9 39 39 39 18 18 18 18
A[3] 45 45 45 39 39 39 39
A[4] 63 63 45 45 45 45
A[5] 18 63 63 63 54
A[6] 81 81 81 63
A[7] 108 108 81
A[8] 54 108
A[9] 72
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Pass 8 – 9th member inserted – upto 9th position array members are sorted

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7 Pass 8
Array A ↓
A[1] 39 9 9 9 9 9 9 9 9
A[2] 9 39 39 39 18 18 18 18 18
A[3] 45 45 45 39 39 39 39 39
A[4] 63 63 45 45 45 45 45
A[5] 18 63 63 63 54 54
A[6] 81 81 81 63 63
A[7] 108 108 81 72
A[8] 54 108 81
A[9] 72 108
A[10] 36
Exercise 1.2
Sort the following numbers using Insertion Sort
39, 9, 45, 63, 18, 81, 108, 54, 72, 36
Pass 9 – 10th member inserted – upto 10th position array members are sorted
Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7 Pass 8 Pass 9
Array A ↓
A[1] 39 9 9 9 9 9 9 9 9 9
A[2] 9 39 39 39 18 18 18 18 18 18
A[3] 45 45 45 39 39 39 39 39 36
A[4] 63 63 45 45 45 45 45 39
A[5] 18 63 63 63 54 54 45
A[6] 81 81 81 63 63 54
A[7] 108 108 81 72 63
A[8] 54 108 81 72
A[9] 72 108 81
A[10] 36 108

Note the un accessed data in the bottom left triangle, due to this the number of comparisons and swaps are
less in insertion sort compared to bubble sort
 Algorithm for Insertion Sort

Uses 2 nested iterations

– outer iteration repeated for n-1 of times for inserting ith member and ordering upto a[i]
- Inner iteration inserts ith member by an upward movement in its ordered position
 Insertion Sort
Note:
❑Insertion sort is easy to implement and efficient on partially sorted
data sets.
❑The time complexity of the algorithm is O(N2).
❑Number of comparisons and exchanges are less compared to
bubble sort algorithm
 1.3 SELECTION SORT
❑It works with the principle of selecting appropriate member(s) for
the positions 1, 2, 3, ... N-1 and swap only once an iteration if
required
❑It is used for sorting files with very large objects.
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Passes →
Array A ↓
A[1] 35
A[2] 33
A[3] 42
A[4] 10
A[5] 14
A[6] 19
A[7] 26
A[8] 44
A[9] 25
A[10] 31
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 1 / pass 1 brings the least value to a[1] after swapping 35 to a[4]
Passes →
Pass 1
Array A ↓
A[1] 35 10
A[2] 33 33
A[3] 42 42
A[4] 10 35
A[5] 14 14
A[6] 19 19
A[7] 26 26
A[8] 44 44
A[9] 25 25
A[10] 31 31
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 2 / pass 2 brings the 2nd least value to a[2] after swapping 33 to a[5]

Passes →
Pass 1 Pass 2
Array A ↓
A[1] 35 10 10
A[2] 33 33 14
A[3] 42 42 42
A[4] 10 35 35
A[5] 14 14 33
A[6] 19 19 19
A[7] 26 26 26
A[8] 44 44 44
A[9] 25 25 25
A[10] 31 31 31
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 3 / pass 3 brings the 3rd least value to a[3] after swapping 42 to a[6]

Passes →
Pass 1 Pass 2 Pass 3
Array A ↓
A[1] 35 10 10 10
A[2] 33 33 14 14
A[3] 42 42 42 19
A[4] 10 35 35 35
A[5] 14 14 33 33
A[6] 19 19 19 42
A[7] 26 26 26 26
A[8] 44 44 44 44
A[9] 25 25 25 25
A[10] 31 31 31 31
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 4 / pass 4 brings the 4th least value to a[4] after swapping 35 to a[9]

Passes →
Pass 1 Pass 2 Pass 3 Pass 4
Array A ↓
A[1] 35 10 10 10 10
A[2] 33 33 14 14 14
A[3] 42 42 42 19 19
A[4] 10 35 35 35 25
A[5] 14 14 33 33 33
A[6] 19 19 19 42 42
A[7] 26 26 26 26 26
A[8] 44 44 44 44 44
A[9] 25 25 25 25 35
A[10] 31 31 31 31 31
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 5 / pass 5 brings the 5th least value to a[5] after swapping 33 to a[7]

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5
Array A ↓
A[1] 35 10 10 10 10 10
A[2] 33 33 14 14 14 14
A[3] 42 42 42 19 19 19
A[4] 10 35 35 35 25 25
A[5] 14 14 33 33 33 26
A[6] 19 19 19 42 42 42
A[7] 26 26 26 26 26 33
A[8] 44 44 44 44 44 44
A[9] 25 25 25 25 35 35
A[10] 31 31 31 31 31 31
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 6 / pass 6 brings the 6th least value to a[6] after swapping 42 to a[10]

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6
Array A ↓
A[1] 35 10 10 10 10 10 10
A[2] 33 33 14 14 14 14 14
A[3] 42 42 42 19 19 19 19
A[4] 10 35 35 35 25 25 25
A[5] 14 14 33 33 33 26 26
A[6] 19 19 19 42 42 42 31
A[7] 26 26 26 26 26 33 33
A[8] 44 44 44 44 44 44 44
A[9] 25 25 25 25 35 35 35
A[10] 31 31 31 31 31 31 42
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 7 / pass 7 brings the 7th least value to a[7] with no swapping
Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7
Array A ↓
A[1] 35 10 10 10 10 10 10 10
A[2] 33 33 14 14 14 14 14 14
A[3] 42 42 42 19 19 19 19 19
A[4] 10 35 35 35 25 25 25 25
A[5] 14 14 33 33 33 26 26 26
A[6] 19 19 19 42 42 42 31 31
A[7] 26 26 26 26 26 33 33 33
A[8] 44 44 44 44 44 44 44 44
A[9] 25 25 25 25 35 35 35 35
A[10] 31 31 31 31 31 31 42 42
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 8 / pass 8 brings the 8th least value to a[8] after swapping 44 to a[9]

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7 Pass 8
Array A ↓
A[1] 35 10 10 10 10 10 10 10 10
A[2] 33 33 14 14 14 14 14 14 14
A[3] 42 42 42 19 19 19 19 19 19
A[4] 10 35 35 35 25 25 25 25 25
A[5] 14 14 33 33 33 26 26 26 26
A[6] 19 19 19 42 42 42 31 31 31
A[7] 26 26 26 26 26 33 33 33 33
A[8] 44 44 44 44 44 44 44 44 35
A[9] 25 25 25 25 35 35 35 35 44
A[10] 31 31 31 31 31 31 42 42 42
 Exercise 1.3
Exercise 1.3 Sort the following numbers using Selection Sort
35, 33, 42, 10, 14, 19, 26, 44, 25, 31
Iteration 9/ pass 9 brings the 9th least value to a[9] after swapping 42 to a[10]

Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7 Pass 8 Pass 9
Array A ↓
A[1] 35 10 10 10 10 10 10 10 10 10
A[2] 33 33 14 14 14 14 14 14 14 14
A[3] 42 42 42 19 19 19 19 19 19 19
A[4] 10 35 35 35 25 25 25 25 25 25
A[5] 14 14 33 33 33 26 26 26 26 26
A[6] 19 19 19 42 42 42 31 31 31 31
A[7] 26 26 26 26 26 33 33 33 33 33
A[8] 44 44 44 44 44 44 44 44 35 35
A[9] 25 25 25 25 35 35 35 35 44 42
A[10] 31 31 31 31 31 31 42 42 42 44
 SELECTION SORT
Note:
❑Selection sort is easy to implement, but not better than Insertion
sort in certain cases.
❑The time complexity of the algorithm is O(N2).
❑Selection sort requires maximum of n-1 exchanges
 1.4 RADIX SORT
❑It is also named as Bucket Sort.
❑The data in the array are repeatedly distributed into groups based
on the digits or the characters forming the data.
❑In general, the distribution proceeds from Least Significant Digit
(LSD) onwards and progresses digit after digit upto Most Significant
Digit(MSD).
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7 387 First data member placed in 7th bucket
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690 2nd data member placed in 0th bucket

Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7 387
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1
Bucket 2
Bucket 3
Bucket 4 234 3rd data member placed in 4th bucket
Bucket 5
Bucket 6
Bucket 7 387
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1
Bucket 2
Bucket 3
Bucket 4 234
Bucket 5 435 4th data member placed in 5h bucket
Bucket 6
Bucket 7 387
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1
Bucket 2
Bucket 3
Bucket 4 234
Bucket 5 435
Bucket 6
Bucket 7 387 567 5th data member placed in 7h bucket
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1
Bucket 2
Bucket 3 123 6th data member placed in 3rd bucket
Bucket 4 234
Bucket 5 435
Bucket 6
Bucket 7 387 567
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1 441 7th data member placed in 1st bucket
Bucket 2
Bucket 3 123
Bucket 4 234
Bucket 5 435
Bucket 6
Bucket 7 387 567
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1 441
Bucket 2 702 8th data member placed in 2nd bucket
Bucket 3 123
Bucket 4 234
Bucket 5 435
Bucket 6
Bucket 7 387 567
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1 441
Bucket 2 702
Bucket 3 123
Bucket 4 234
Bucket 5 435
Bucket 6 826 9th data member placed in 6th bucket
Bucket 7 387 567
Bucket 8
Bucket 9
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – LSD based processing of each data (separate the last digit – and in its respective bucket, place the data)

Bucket 0 690
Bucket 1 441
Bucket 2 702
Bucket 3 123
Bucket 4 234
Bucket 5 435
Bucket 6 826
Bucket 7 387 567
Bucket 8
Bucket 9 999 10th data member placed in 9th bucket
 Exercise 1.4
Sort the following numbers using Radix Sort
387, 690, 234, 435, 567, 123, 441, 702, 826, 999
n= 10; Radix r = 10; No. of Digits=3
Pass 1 of Radix Sort – completion – collect the data from bucket 0 to bucket 9 (left to right) in order in to the resulting array

Bucket 0 690
Bucket 1 441
Bucket 2 702
Bucket 3 123
Bucket 4 234
Bucket 5 435
Bucket 6 826
Bucket 7 387 567
Bucket 8
Bucket 9 999

Array after Pass1: 690, 441, 702, 123, 234, 435, 826, 387, 567, 999
 Exercise 1.4
Pass 1 Results: 690, 441, 702, 123, 234, 435, 826, 387, 567, 999
Pass 2 – of Radix Sort – 2nd Significant Digit based processing
Bucket 0 702
Bucket 1
Bucket 2 123 826
Bucket 3 234 435
Bucket 4 441
Bucket 5
Bucket 6 567
Bucket 7
Bucket 8 387
Bucket 9 690 999
Pass 2 Results: 702, 123, 826, 234, 435, 441, 567, 387, 690, 999
 Exercise 1.4
Pass 2 Results: 702, 123, 826, 234, 435, 441, 567, 387, 690, 999
Pass 3 of Radix Sort – MSD based processing

Bucket 0
Bucket 1 123
Bucket 2 234
Bucket 3 387
Bucket 4 435 441
Bucket 5 567
Bucket 6 690
Bucket 7 702
Bucket 8 826
Bucket 9 999

Pass 3 (Final) Results: 123, 234, 387, 435, 441, 567, 690, 702, 826, 999
 Radix Sorting
Note:
❑The time complexity of the radix sort algorithm is O(k×n).
❑k is the number of digits in the largest data and n is the number of data

❑Radix sort is simple and takes less time to sort.

❑However, it consumes additional memory for the buckets (upto
m×n, m-radix number, n-number of data)
 1.5 Heap Sort
❑Heap sort belongs to the family of sorting by selection.
❑It performs repeated selection of largest data in the array by
heapify process (of complete binary tree representation) and places
it in the output list.
❑Heap sort is built on heap data structure (a complete binary tree
with the parent node having data greater or equal to that of the
children at every level resulting to the placement of the largest data
of all at the root)
 1.5 Heap Sort
Heap sort proceeds in two phases in each iteration
• (Heapify) Build heap using bottom-up processing
• Repeat
o Swap top (largest element) and last element
o Decrease heap size
o Heapify
Array to binary tree or binary Heap conversion
a[1]

a[2] a[3]
a[8] = {2, 4, 7, 8, 16, 9, 13, 11}
a[4]
a[5] a[6] a[7]
a[8]

Array processed in non-linear or tree sequence

• Left child of a[i] = a[2i]
• Right child of a[i] = a[2i+1]
• Parent of a[i] = a[i/2]
Heapify – MaxHeap or MinHeap
 Min-Heap and Max-Heap - Definition
1. A min-heap is a binary tree such that the data contained in each
node is less than (or equal to) the data in that node’s children. The
binary tree is complete
2. A max-heap is a binary tree such that the data contained in each
node is greater than (or equal to) the data in that node’s children. -
The binary tree is complete
 Max Heapify – Complete Binary Tree / Heap

Input : complete binary tree not heapified

Output maxheapified complete binary tree
Complete Binary Tree: tree obtained by filling data in circles / nodes
of the tree from root top to bottom proceeding left to right manner
in every level
Heapify process starts at the bottom most right sub tree and
proceeds towards left and above sub trees till root
 Heapify – Max Tree

- In every triangle subtree, maximum value brought up to the parent by swapping, if required with the highest valued child.
- The swapped value to the child will be adjusted with the below triangles if required to maintain maxheap
Identify Max Heaps from the following trees A, B, C, D
Identify Min Heaps from the following trees
 Heapsort - Stepwise
Heapsort –steps
1.MaxHeap
2.Swap with last member
3.Adjust heap due to root swap or change
4. Detach last member
5.Repeat steps 1 to 4
 Heapsort – Exercise 1.5

2 2 8

3 7 8 7 2 7

1 8 5 6 1 3 5 6 1 3 5 6

8 6 7

3 7 3 7 3 6

5 6 1 2 5 8 5 8
1 2 1 2
Input : (2, 3, 7, 1, 8, 5, 6)
After Max Heap: (8, 3, 7, 1, 2, 5, 6)
After swap and detach: (6, 3, 7, 1, 2, 5, 8)
After Adjust : (7, 3, 6, 1, 2, 5, 8)
 Heapsort – Exercise 1.5

2 2 8

3 7 8 7 2 7

6 1 3 5 6 1 3 5 6
1 8 5
Max Heapify a[7] : (2, 8, 7, 1, 3, 5, 6) Max Heapify a[7]: (8, 2, 7, 1, 3, 5, 6)
Input a[7]: (2, 3, 7, 1, 8, 5, 6)

8 6 7

3 7 3 7 3 6

1 2 5 8 1 2 5 8
1 2 5 6 Iteration1 result a[7]: (7, 3, 6, 1, 2, 5, 8)
Swap & Detach largest a[7]: (6, 3, 7, 1, 2, 5, 8)
Max Heap and adjust a[7]: (8, 3, 7, 1, 2, 5, 6)
Heapsort – Exercise 1.5
 Exercise 1.5
Sort the following numbers using Heap Sort
A[11] = {11, 1, 5, 7, 6, 12, 17, 8, 4, 10, 2}
Tree representation of the Data Completion of Heapify and swap
(before Pass 1) (After Pass 1)
11
2
/ \
/ \
10 5
10 11
/ \ / \ / \ / \
7 6 12 17 8 1 12 5
/ \ / \ / \ / \
8 4 10 2 7 4 6 17
 Iterationwise Heapsort results
Passes →
Pass 1 Pass 2 Pass 3 Pass 4 Pass 5 Pass 6 Pass 7 Pass 8 Pass 9 Pass 10
Array A ↓
A[1] 11 2 1 4 7 1 2 1 2 1 1
A[2] 1 10 10 10 4 7 1 2 4 2 2
A[3] 5 11 2 1 5 5 5 5 1 4 4
A[4] 7 8 8 8 8 4 4 4 5 5 5
A[5] 6 1 6 6 6 6 6 6 6 6 6
A[6] 12 12 11 2 2 2 7 7 7 7 7
A[7] 17 5 5 5 1 8 8 8 8 8 8
A[8] 8 7 7 7 10 10 10 10 10 10 10
A[9] 4 4 4 11 11 11 11 11 11 11 11
A[10] 10 6 12 12 12 12 12 12 12 12 12
A[11] 2 17 17 17 17 17 17 17 17 17 17
 Algorithm for Heap Sort

Heap-Sort(A, N)
heapify(A, I, N)
Step 1: buildHeap(A)
Step 1: left = 2*I + 1 and right = 2*I + 2
Step 2: FOR I = N downto 2 do
Step 2: IF (left <= N and A[left] > A[I])
Step 3: SWAP A[1] with A[I]
Step 3: largest = left
Step 4: heapify(A, 0, I)
Step 4: ELSE largest = I
Step 7: ENDFOR
Step 5: IF (right < max and A[right] > A[largest])
Step 8: END
Step 6: largest = right
Step 7: IF (largest != I)
buildHeap(A)
Step 8: SWAP A[I] and A[largest]
Step 1: FOR I = N/2 downto 1 do
Step 9: heapify(A, largest, max)
Step 2: heapify(A, I, N)
Step 10: END
Step 3: END
 Heapsort
Note:
❑The complexity of Heapsort = O(n×logn).
❑It is a simple, fast and stable sorting algorithm.
❑It can be used for large set of data efficiently.
 1.6 MERGE SORT
❑It uses divide and conquer strategy.
❑The objective of sorting is achieved by dividing the input array into
smaller partitions recursively and then merging the partitions to
order the data.
 Exercise 1.6
Sort the following numbers using Merge Sort
A[8] = {12, 56, 1, 34, 89, 78, 43, 10}
Tree of recursive partitioning (Top to bottom)

Mergesort(A,1,8)
[12,56,1,34,89,78,43,10]

Mergesort(A,1,4) Mergesort(A,5,8)
[12,56,1,34] [89,78,43,10]

Mergesort(A,1,2) Mergesort(A,3,4) Mergesort(A,5,6) Mergesort(A,7,8)

[12,56] [1,34] [89,78] [43,10]

Mergesort(A,1,1) Mergesort(A,3,3) Mergesort(A,5,5) Mergesort(A,7,7)Mergesort(A,8,8)

[12] [1] [89] [43] [10]

Mergesort(A,2,2) Mergesort(A,4,4) Mergesort(A,6,6)

[56] [34] [78]
 Exercise 1.6
Tree of recursive Merging (Bottom to Top)
Merge(A,1,4,8)
[1,10,12,34,43,56,78,89]

Merge(A,1,2,4) Merge(A,5,6,8)
[1,12,34,56] [10,43,78,89]

Merge(A,1,1,2) Merge(A,3,3,4) Merge(A,5,5,6) Merge(A,7,7,8)

[12,56] [1,34] [78,89] [10,43]

Mergesort(A,1,1) Mergesort(A,3,3) Mergesort(A,5,5) Mergesort(A,7,7)Mergesort(A,8,8)

[12] [1] [89] [43] [10]

Mergesort(A,2,2) Mergesort(A,4,4) Merge

sort(A,6,6)
[56] [34] [78]
 Algorithm for Merge Sort
MERGE(A, BEG,MID,END) MERGE-SORT(A, BEG, END)
Step 1: SET I=BEG; J=MID+1; K=1 Step 1: IF BEG < END, then
Step 2: Repeat While (I<=MID) AND (J<=END) Step 2: MID = (BEG + END ) / 2
Step 3: IF A[I] < A[J] then B[K]=A[I]; I++; K++; Step 3: CALL MERGE-SORT(A, BEG, MID)
Step 4: ELSE B[K]=A[J]; J++; K++; Step 4: CALL MERGE-SORT(A, MID+1, END)
Step 7: ENDRepeat Step 5: CALL MERGE(A, BEG, MID, END)
Step 8: IF I > MID then Step 6: END
Step 9: Repeat While J<=END
Step 10: B[K]=A[J]; J++; K++;
Step 11: ENDRepeat
Step 12: ELSE
Step 9: Repeat While I<=MID
Step 10: B[K]=A[I]; I++; K++;
Step 11: ENDRepeat
Step 12: END IF
Step 13: Repeat While K < J
Step 14: B[K] = A[J]
Step 15: END Repeat
Step 16: END
 1.6 MERGE SORT
Note:
❑The time complexity of Merge sort is O(nlogn).
❑It is a simple recursive and fast sorting algorithm but requires
additional array (storage) B to store the intermediate sorted result.
 1.7 SHELL SORT
❑It is a generalisation of insertion sort invented by Donald Shell, also
named as diminishing increment / gapsized sort
❑It has been improved over insertion sort in two ways
❑Compares elements separated by a gap sized distance and not at one step neighbour
❑Comparisons and exchanges diminish over the passes / iterations
 Exercise 1.6
Sort the following numbers using Shell Sort
A[11] = {11, 1, 5, 7, 6, 12, 17, 8, 4, 10, 2}
Processing at each pass – Arrange the elements of the array in the
form of table and insertion sort

Each pass executed with diminishing increment {6, 3, 2, 1} and insertion

sort
◦ Insertion sort every 6th element
◦ Insertion sort every 3rd element
◦ Insertion sort every 2nd element
◦ Insertion sort every element in normal way
 Exercise 1.6
Pass 1 (pair 1 from 2 partitions) – Sort every 6th element

Increment / gap_size = (11+1) / 2 = 6 (no. of members in each partition)

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 5 7 6 12 17 8 4 10 2

Pass 1 (pair 2 from 2 partitions) - Sort every 6th element

Increment / gap_size = (11+1) / 2 = 6

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 5 7 6 12 17 8 4 10 2
 Exercise 1.6
Pass 1 (pair 3 from 2 partitions) - Sort every 6th element
Increment / gap_size = (11+1) / 2 = 6
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 5 7 6 12 17 8 4 10 2

Pass 1 (pair 3 swapped)

Increment / gap_size = (11+1) / 2 = 6
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 6 12 17 8 5 10 2
 Exercise 1.6

Pass 1 (pair 4 from 2 partitions) - Sort every 6th element

Increment / gap_size = (11+1) / 2 = 6
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 6 12 17 8 5 10 2
 Exercise 1.6
Pass 1 (pair 5 from 2 partitions) - Sort every 6th element
Increment / gap_size = (11+1) / 2 = 6
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 6 12 17 8 5 10 2

Pass 1 (pair 5 swapped)

Increment / gap_size = (11+1) / 2 = 6
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 2 12 17 8 5 10 6
 Exercise 1.6

Pass 1 (6th member in partition1 – no pair in partition 2 – no change) - Sort every 6th
element
Increment / gap_size = (11+1) / 2 = 6
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 2 12 17 8 5 10 6
 Exercise 1.6

Pass 1 result
Increment / gap_size = (11+1) / 2 = 6
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
Before 11 1 5 7 6 12 17 8 4 10 2
After 11 1 4 7 2 12 17 8 5 10 6
Pass 1 Outcome A[11] = 11, 1, 4, 7, 2, 12, 17, 8, 5, 10, 6
 Exercise 1.6
Pass 2 – input – Sort every 3rd element
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 2 12 17 8 5 10 6
Increment / Gap size = (6+1) / 2 = 3 (no. of members in each partition)
4 partitions – first members sorted in order
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 2 12 17 8 5 10 6
7 1 4 10 2 12 11 8 5 17 6
 Exercise 1.6
Pass 2 - input
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 2 12 17 8 5 10 6

Increment / Gap size = (6+1) / 2 = 3 - (4 partitions – second members sorted in order)

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
7 1 4 10 2 12 11 8 5 17 6
7 1 4 10 2 12 11 6 5 17 8
 Exercise 1.6
Pass 2 - input
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
11 1 4 7 2 12 17 8 5 10 6
Increment / Gap size = (6+1) / 2 = 3 - (4 partitions – third members sorted in order)
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
7 1 4 10 2 12 11 6 5 17 8
7 1 4 10 2 5 11 6 12 17 8
Pass 2 Outcome A[11] = 7, 1, 4, 10, 2, 5, 11, 6, 12, 17, 8
 Exercise 1.6
Pass 3 - input
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
7 1 4 10 2 5 11 6 12 17 8
Increment / Gap size = (3+1) / 2 = 2 (6 partitions each with 2 members except last with one
member)
First member in each partition sorted in order
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
7 1 4 10 2 5 11 6 12 17 8
2 1 4 10 7 5 8 6 11 17 12
Second member in each partition sorted in order
2 1 4 10 7 5 8 6 11 17 12
2 1 4 5 7 6 8 10 11 17 12

Pass 3 Outcome A[11] = 2, 1, 4, 5, 7, 6, 8, 10, 11, 11, 12

 Exercise 1.6
Pass 4 - input
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
2 1 4 5 7 6 8 10 11 17 12
Increment / Gap size = (2+1) / 2 = 1 (all members in single partition sorted in order)
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]
2 1 4 5 7 6 8 10 11 17 12
1 2 4 5 6 7 8 10 11 12 17

Pass 4 Outcome A[11] = {1, 2, 4, 5, 6, 7, 8, 10, 11, 12, 17}

Gap size / increments for each of the 4 passes = {6, 3, 2, 1}
Shell sort Algorithm in comparison with Insertion sort algorithm
 SHELL SORT
Note:
❑Performance of Shell sort depends on the choice of increments.
❑Time complexity O(N2).
 1.8. Quick Sort
❑A large array is partitioned into two arrays one of which holds
values smaller than the pivot value, and another array holds values
greater than the pivot value.
❑Quicksort partitions an array and then calls itself recursively twice
to sort the two resulting subarrays.
Quick Sort – recursive main algorithm

100
 Quick Sort – Partitioning algorithm
Step 1 − Choose the first indexed value as pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high index
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

101
Partitioning - example

102
 1.8. Quick Sort
Note:
❑This algorithm is quite efficient for large-sized data sets.
❑Its average and worst-case complexity are O(nLogn) and O(n2),
respectively
Comparison of sorting algorithms
 Linear search
❑A linear search sequentially checks each element of the list until it
finds an element that matches the target value.
❑If the algorithm reaches the end of the list, the search terminates
unsuccessfully
 Linear Search Algorithm
Linear search for an element in an array of N elements :
• STEP 1 : Start from the first element of array and one by one compare the query element with each element
of the array.
• STEP 2 : If the query element matches with an element, return the index.
• STEP 3 : If the query element doesn’t match with any of elements, return failure.

106
 Linear Search Algorithm

Successful Search:

Un Successful Search:

107
 Binary Search - Algorithm
❑ The idea of binary search is to use the information that the array is sorted
and reduce the time complexity to O(Log n)
❑ Algorithm steps
❑Sort the array elements.
❑Search a sorted array by repeatedly dividing the search interval in half.
❑Begin with an interval covering the whole array.
❑If the value of the search key is less than the item in the middle of the interval, narrow the interval to the
lower half.
❑Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty

108
Binary Search - Example

109
 Linear Search Vs Binary Search

BASIS FOR COMPARISON LINEAR SEARCH BINARY SEARCH

Time Complexity O(N) O(log 2 N)
Best case time First Element O(1) Center Element O(1)
Prerequisite for an array Not required Array must be in sorted order
Worst case for N number of elements N comparisons are required Only log2N comparisons

110