Unit 4: Searching and Sorting

UNIT 4
SEARCHING AND SORTING: 6 HOURS

DR. NEEPA SHAH 1

SYLLABUS CONTENT

 Searching:
 Linear Search, Binary search
 Analysis of searching Techniques
 Sorting:
 Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort
 Analysis of Sorting Techniques
 Comparison of Sorting Techniques
 Hashing:
 Hashing Techniques, Different Hash Functions, Collision & Collision Resolution Techniques

DR. NEEPA SHAH 2

Dr. Neepa Shah 1

Unit 4: Searching and Sorting

WHAT IS SORTING?

 Examples:
 Sorting Books in Library
 Sorting Individuals by Height (Feet and Inches)
 Sorting Movies in Blockbuster (Alphabetical)
 Sorting Numbers (Sequential)

DR. NEEPA SHAH 3

CLASSIFICATION

 Sorting algorithms are often classified by:

 Computational Complexity
 Computational Complexity of Swaps
 Memory usage
 Recursion
 Stability

DR. NEEPA SHAH 4

Dr. Neepa Shah 2

Unit 4: Searching and Sorting

SORTING ALGORITHMS
 Bubble Sort
 Selection Sort
 Insertion Sort
 Shell Sort
 Merge Sort
 Quick Sort
 Heap Sort
 Bucket Sort
 Radix Sort
DR. NEEPA SHAH 5

BUBBLE SORT

 One of the simplest sorting algorithm

 Also known as Exchange sort

DR. NEEPA SHAH 6

Dr. Neepa Shah 3

Unit 4: Searching and Sorting

9, 6, 2, 12, 11, 9, 3, 7
6, 9, 2, 12, 11, 9, 3, 7
6, 2, 9, 12, 11, 9, 3, 7
6, 2, 9, 12, 11, 9, 3, 7
6, 2, 9, 11, 12, 9, 3, 7
6, 2,
BUBBLE SORT EXAMPLE
9, 11, 9, 12, 3, 7
6, 2,
DR. NEEPA SHAH
9, 11, 9, 3, 12, 7 7

6, 2, 9, 11, 9, 3, 7, 12

BUBBLE SORT EXAMPLE CONTD.

First Pass
6, 2, 9, 11, 9, 3, 7, 12
Second Pass

6, 6,
2, 2, 9, 9,
11,3,
11,
9,7,
11,
3,11,
7, 12

DR. NEEPA SHAH 8

Dr. Neepa Shah 4

Unit 4: Searching and Sorting

BUBBLE SORT EXAMPLE CONTD.

First Pass
6, 2, 9, 11, 9, 3, 7, 12
Second Pass

Third Pass
2, 6, 9, 9, 3, 7, 11, 12
2, 6, 9, 3,
9, 7,
3, 9,
9, 7, 11, 12

DR. NEEPA SHAH 9

BUBBLE SORT EXAMPLE CONTD.

First Pass
6, 2, 9, 11, 9, 3, 7, 12
Second Pass

Third Pass
2, 6, 9, 9, 3, 7, 11, 12
Fourth Pass
2, 6, 9, 3, 7, 9, 11, 12
2, 6, 9,
3, 3, 9,
9,
7, 7, 9, 11, 12

DR. NEEPA SHAH 10

Dr. Neepa Shah 5

Unit 4: Searching and Sorting

BUBBLE SORT EXAMPLE CONTD.

First Pass
6, 2, 9, 11, 9, 3, 7, 12
Second Pass

Third Pass
2, 6, 9, 9, 3, 7, 11, 12
Fourth Pass
2, 6, 9, 3, 7, 9, 11, 12
Fifth Pass
2, 6, 3, 7, 9, 9, 11, 12
2, 6,
3, 3,
6, 7, 9, 9, 11, 12
DR. NEEPA SHAH 11

BUBBLE SORT EXAMPLE CONTD.

First Pass
6, 2, 9, 11, 9, 3, 7, 12
Second Pass

Third Pass
2, 6, 9, 9, 3, 7, 11, 12
Fourth Pass
2, 6, 9, 3, 7, 9, 11, 12
Fifth Pass
2, 6, 3, 7, 9, 9, 11, 12
Sixth Pass
2, 3, 6, 7, 9, 9, 11, 12
DR. NEEPA SHAH
2, 3, 6, 7, 9, 9, 11, 12 12

Dr. Neepa Shah 6

Unit 4: Searching and Sorting

BUBBLE SORT PROCEDURE

1. Do steps 2-3 for i= n-1 down to 1

2. Do step 3 for j=0 upto i-1
3. If the 2 consecutive elements sj and sj+1, are out of order swap them

DR. NEEPA SHAH 13

BUBBLE SORT ALGORITHM

for(i = SIZE-1; i > 0; i--) {

for(i = 0; i < n; i++) {
for(j = 0; j < i; j++) {
for(j = 1; j < (n-i); j++) {
if(a[j] > a[j+1]) { if(a[j-1] > a[j]) {
t = a[j]; t = a[j-1];
a[j]=a[j+1]; a[j-1]=a[j];
a[j+1]=t; a[j]=t;
} }
}
}
}
}

DR. NEEPA SHAH 14

Dr. Neepa Shah 7

Unit 4: Searching and Sorting

BUBBLE SORT

 Pros: Simplicity and ease of implementation

 Cons: Horribly Inefficient

DR. NEEPA SHAH 15

EFFICIENT BUBBLE SORT

for(i = 0; i < n; i++) {

flag = 0;
for(j = 1; j < (n-i); j++) {
if(a[j-1] > a[j]) {
t = a[j-1];
a[j-1]=a[j];
a[j]=t;

flag = 1;
}
}

if (flag==0) break;
}

DR. NEEPA SHAH 16

Dr. Neepa Shah 8

Unit 4: Searching and Sorting

SUMMARY

 “Bubble Up” algorithm will move largest value to its correct location (to the right)
 Repeat “Bubble Up” until all elements are correctly placed:
 Maximum of N-1 times
 Can finish early if no swapping occurs
 We reduce the number of elements we compare each time one is correctly placed

DR. NEEPA SHAH 17

SELECTION SORT

 The idea of selection sort is rather simple.

 We repeatedly find the next largest (or smallest) element in the array and move it to its final position
in the sorted array.

 We begin by selecting the largest element and moving it to the highest index position. We can do this
by swapping the element at the highest index and the largest element. The process stops when the
effective size of the array becomes 1

DR. NEEPA SHAH 18

Dr. Neepa Shah 9

Unit 4: Searching and Sorting

SELECTION SORT - EXAMPLE

32 91 12 55 74 73 18

DR. NEEPA SHAH 19

SELECTION SORT - EXAMPLE

32 91 12 55 74 73 18

DR. NEEPA SHAH 20

Dr. Neepa Shah 10

Unit 4: Searching and Sorting

SELECTION SORT - EXAMPLE

SWAP !

32 91 12 55 74 73 18

DR. NEEPA SHAH 21

SELECTION SORT - EXAMPLE

12 91 32 55 74 73 18

DR. NEEPA SHAH 22

Dr. Neepa Shah 11

Unit 4: Searching and Sorting

SELECTION SORT - EXAMPLE

12 91 32 55 74 73 18

DR. NEEPA SHAH 23

SELECTION SORT - EXAMPLE

SWAP !

12 91 32 55 74 73 18

DR. NEEPA SHAH 24

Dr. Neepa Shah 12

Unit 4: Searching and Sorting

SELECTION SORT - EXAMPLE

12 18 32 55 74 73 91

DR. NEEPA SHAH 25

SELECTION SORT - EXAMPLE

NO SWAPPING !

12 18 32 55 74 73 91

DR. NEEPA SHAH 26

Dr. Neepa Shah 13

Unit 4: Searching and Sorting

SELECTION SORT - EXAMPLE

12 18 32 55 74 73 91

DR. NEEPA SHAH 27

SELECTION SORT - EXAMPLE SWAP !

12 18 32 55 74 73 91

DR. NEEPA SHAH 28

Dr. Neepa Shah 14

Unit 4: Searching and Sorting

SELECTION SORT - EXAMPLE

12 18 32 55 73 74 91

DR. NEEPA SHAH 29

SELECTION SORT - EXAMPLE

12 18 32 55 73 74 91

DR. NEEPA SHAH 30

Dr. Neepa Shah 15

Unit 4: Searching and Sorting

SELECTION SORT - EXAMPLE NO SWAPPING !

12 18 32 55 73 74 91

DR. NEEPA SHAH 31

SELECTION SORT - EXAMPLE

12 18 32 55 73 74 91

DR. NEEPA SHAH 32

Dr. Neepa Shah 16

Unit 4: Searching and Sorting

SELECTION SORT PROCEDURE

1. Do steps 2-3 for i= n-1 down to 1

2. Locate the index m of the largest / smallest element among {s0…sj}
3. Swap si and sm

DR. NEEPA SHAH 33

SELECTION SORT ALGORITHM

void sort(int a[])

{
for(i = SIZE-1; i > 0 ; i--)
{
m = 0;
for(j = 1; j <= i; j++)
{
if(a[j] > a[m])
m = j;
}
swap(a, i, m);
}
}

DR. NEEPA SHAH 34

Dr. Neepa Shah 17

Unit 4: Searching and Sorting

INSERTION SORT

 Insertion sort keeps making the left side of the array sorted until the whole array is sorted.

It sorts the values seen so far and repeatedly inserts unseen values in the array into the left
sorted array.

 The insertion sort algorithm is the sort unknowingly used by most card players

DR. NEEPA SHAH 35

INSERTION SORT CONTD.

 while some elements unsorted:

 Using linear search, find the location in the sorted portion where the 1st element of
the unsorted portion should be inserted
 Move all the elements after the insertion location up one position to make space for
the new element

69

38 45
60 60
66 45
66 79 47 13 74 36 21 94 22 57 16 29 81

the fourth iteration of this loop is shown here

DR. NEEPA SHAH 36

Dr. Neepa Shah 18

Unit 4: Searching and Sorting

REVIEW: ONE STEP OF INSERTION SORT

sorted next to be inserted

3 4 7 12 14 14 20 21 33 38 10 55 9 23 28 16
temp
less than 10
10

3 4 7 10 12 14 14 20 21 33 38 55 9 23 28 16

sorted

DR. NEEPA SHAH 37

INSERTION SORT CONTD.

An insertion sort partitions the array into two regions

DR. NEEPA SHAH 38

Dr. Neepa Shah 19

Unit 4: Searching and Sorting

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

DR. NEEPA SHAH 39

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

DR. NEEPA SHAH 40

Dr. Neepa Shah 20

Unit 4: Searching and Sorting

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

DR. NEEPA SHAH 41

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

DR. NEEPA SHAH 42

Dr. Neepa Shah 21

Unit 4: Searching and Sorting

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

DR. NEEPA SHAH 43

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

DR. NEEPA SHAH 44

Dr. Neepa Shah 22

Unit 4: Searching and Sorting

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

DR. NEEPA SHAH 45

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

DR. NEEPA SHAH 46

Dr. Neepa Shah 23

Unit 4: Searching and Sorting

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

2 3 4 8 9 6

DR. NEEPA SHAH 47

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

2 3 4 8 9 6

DR. NEEPA SHAH 48

Dr. Neepa Shah 24

Unit 4: Searching and Sorting

EXAMPLE OF INSERTION SORT

8 2 4 9 3 6

2 8 4 9 3 6

2 4 8 9 3 6

2 4 8 9 3 6

2 3 4 8 9 6

2 3 4 6 8 9 done
DR. NEEPA SHAH 49

INSERTION SORT EXAMPLE

 5 7 0 3 4 2 6 1 (0)
 5 7 0 3 4 2 6 1 (0)
 0 5 7 3 4 2 6 1 (2)
 0 3 5 7 4 2 6 1 (2)
 0 3 4 5 7 2 6 1 (2)
 0 2 3 4 5 7 6 1 (4)
 0 2 3 4 5 6 7 1 (1)
 0 1 2 3 4 5 6 7 (6)

DR. NEEPA SHAH 50

Dr. Neepa Shah 25

Unit 4: Searching and Sorting

An insertion sort of an array of five integers

DR. NEEPA SHAH 51

INSERTION SORT PROCEDURE

1. Do steps 2-4 for i= 1 upto n-1

2. Hold the element s
3. Locate the least index j for which sj >= si
4. Shift the subsequence {sj … si-1} up one position to {sj+1 … si}
5. Copy the held value of si into sj

DR. NEEPA SHAH 52

Dr. Neepa Shah 26

Unit 4: Searching and Sorting

INSERTION SORT ALGORITHM

void insertionSort(int[] a) {
for (int i = 1; i < SIZE; i++) {
int ai = a[i], j;

for (j = i; j > 0 && a[j-1] > ai; j--) {

a[j] = a[j–1];
}
a[j] = ai;
}
}

DR. NEEPA SHAH 53

INSERTION SORT: NUMBER OF COMPARISONS

# of Sorted Best case Worst case
Elements

0 0 0

1 1 1

2 1 2

… … …

n-1 1 n-1
n-1 n(n-1)/2

If the sequence is nearly sorted, then insertion sort will run nearly in O(n) time.

DR. NEEPA SHAH 54

Dr. Neepa Shah 27

Unit 4: Searching and Sorting

DIVIDE AND CONQUER STRATEGY

DR. NEEPA SHAH 55

DIVIDE-AND-CONQUER

 Divide and Conquer is a method of algorithm design.

 This method has three distinct steps:

 Divide: If the input size is too large to deal with in a straightforward manner, divide the data into two or
more disjoint subsets.
 Recur: Use divide and conquer to solve the sub-problems associated with the data subsets.
 Conquer: Take the solutions to the sub-problems and “merge” these solutions into a solution for the original
problem.

DR. NEEPA SHAH 56

Dr. Neepa Shah 28

Unit 4: Searching and Sorting

MERGE-SORT

 Algorithm:
 Divide
 Recur: Recursive sort sequences S1 and S2.
 Conquer: Put back the elements into S by merging the sorted sequences S1 and S2 into a unique
sorted sequence.

DR. NEEPA SHAH 57

MERGE-SORT EXAMPLE

DR. NEEPA SHAH 58

Dr. Neepa Shah 29

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

DR. NEEPA SHAH 59

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

DR. NEEPA SHAH 60

Dr. Neepa Shah 30

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23

DR. NEEPA SHAH 61

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23

Merge

DR. NEEPA SHAH 62

Dr. Neepa Shah 31

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23

23

Merge

DR. NEEPA SHAH 63

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23

23 98

Merge

DR. NEEPA SHAH 64

Dr. Neepa Shah 32

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98

DR. NEEPA SHAH 65

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98

Merge

DR. NEEPA SHAH 66

Dr. Neepa Shah 33

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14

Merge

DR. NEEPA SHAH 67

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

Merge

DR. NEEPA SHAH 68

Dr. Neepa Shah 34

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

Merge

DR. NEEPA SHAH 69

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14

Merge

DR. NEEPA SHAH 70

Dr. Neepa Shah 35

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14 23

Merge

DR. NEEPA SHAH 71

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14 23 45

Merge

DR. NEEPA SHAH 72

Dr. Neepa Shah 36

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

98 23 45 14

23 98 14 45

14 23 45 98

Merge

DR. NEEPA SHAH 73

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14

23 98 14 45

14 23 45 98

DR. NEEPA SHAH 74

Dr. Neepa Shah 37

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67

23 98 14 45

14 23 45 98

DR. NEEPA SHAH 75

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67

23 98 14 45

14 23 45 98 Merge

DR. NEEPA SHAH 76

Dr. Neepa Shah 38

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67

23 98 14 45 6

14 23 45 98 Merge

DR. NEEPA SHAH 77

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67

23 98 14 45 6 67

14 23 45 98 Merge

DR. NEEPA SHAH 78

Dr. Neepa Shah 39

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67

14 23 45 98

DR. NEEPA SHAH 79

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67

14 23 45 98 Merge

DR. NEEPA SHAH 80

Dr. Neepa Shah 40

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33

14 23 45 98 Merge

DR. NEEPA SHAH 81

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 Merge

DR. NEEPA SHAH 82

Dr. Neepa Shah 41

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98

Merge

DR. NEEPA SHAH 83

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6

Merge

DR. NEEPA SHAH 84

Dr. Neepa Shah 42

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33

Merge

DR. NEEPA SHAH 85

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42

Merge

DR. NEEPA SHAH 86

Dr. Neepa Shah 43

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

Merge

DR. NEEPA SHAH 87

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

DR. NEEPA SHAH Merge 88

Dr. Neepa Shah 44

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

DR. NEEPA SHAH Merge 89

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14

DR. NEEPA SHAH Merge 90

Dr. Neepa Shah 45

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23

DR. NEEPA SHAH Merge 91

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33

DR. NEEPA SHAH Merge 92

Dr. Neepa Shah 46

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42

DR. NEEPA SHAH Merge 93

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45

DR. NEEPA SHAH Merge 94

Dr. Neepa Shah 47

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67

DR. NEEPA SHAH Merge 95

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67 98

DR. NEEPA SHAH Merge 96

Dr. Neepa Shah 48

Unit 4: Searching and Sorting

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42

23 98 14 45 6 67 33 42

14 23 45 98 6 33 42 67

6 14 23 33 42 45 67 98

DR. NEEPA SHAH 97

98 23 45 14 6 67 33 42

6 14 23 33 42 45 67 98

DR. NEEPA SHAH 98

Dr. Neepa Shah 49

Unit 4: Searching and Sorting

EXAMPLE

DR. NEEPA SHAH 99

EXAMPLE CONTD.

DR. NEEPA SHAH 100

Dr. Neepa Shah 50

Unit 4: Searching and Sorting

MERGE SORT ALGORITHM

 Overview:
 Split array into two halves
 Sort the left half (recursively)
 Sort the right half (recursively)
 Merge the two sorted halves

DR. NEEPA SHAH 101

MERGE SORT PROCEDURE

1. If q-p > 1 do steps 2-5 (i.e. p < q)

2. Split s into 2 subsequences, a = {sp … sm-1} and b = {sm … sq-1}, where m = (p + q) / 2
3. Sort a
4. Sort b
5. Merge a and b back into s, preserving order

DR. NEEPA SHAH 102

Dr. Neepa Shah 51

Unit 4: Searching and Sorting

MERGE SORT ALGORITHM

void sort(int a[],int p, int q)

{
if (p > q)
return;

Call from main

int m = (p + q) / 2;
sort (a, 0, n-1)
sort(a, p, m);
sort(a, m+1, q);
merge (a, p, m, q);
}

DR. NEEPA SHAH 103

MERGE FUNCTION
void merge(int arr[], int low, int mid, int high)
{
int i, m, k, l, temp[MAX];
l=low;
i=low;
m=mid+1;
while((l<=mid)&&(m<=high))
{
if(arr[l]<=arr[m])
{
temp[i]=arr[l];
l++;
}
else
{
temp[i]=arr[m];
m++;
}
i++;
}

DR. NEEPA SHAH 104

Dr. Neepa Shah 52

Unit 4: Searching and Sorting

MERGE FUNCTION CONTD.

if(l>mid)
{
for(k=m;k<=high;k++)
{
temp[i]=arr[k];
i++;
}
}
else
{
for(k=l;k<=mid;k++)
{
temp[i]=arr[k];
i++;
}
}

for(k=low;k<=high;k++)
{
arr[k]=temp[k];
}
}
DR. NEEPA SHAH 105

RUNNING TIME OF MERGE-SORT

 At each level in the binary tree created for Merge Sort, there are n elements, with O(1) time spent at each
element
 → O(n) running time for processing one level
 The height of the tree is O(log n)

 Therefore, the time complexity is O(nlog n)

DR. NEEPA SHAH 106

Dr. Neepa Shah 53

Unit 4: Searching and Sorting

QUICK-SORT

1) Divide : If the sequence S has 2 or more elements, select an element x from S to be your pivot. Any arbitrary
element, like the last, will do. Remove all the elements of S and divide them into 3 sequences:
L, holds S’s elements less than x
E, holds S’s elements equal to x
G, holds S’s elements greater than x
2) Recurse: Recursively sort L and G
3) Conquer: Finally, to put elements back into S in order, first inserts the elements of L, then those of E, and those of G.

DR. NEEPA SHAH 107

IDEA OF QUICK SORT

1) Select: pick an element

2) Divide: rearrange elements so that x goes to its final position E

3) Recurse and Conquer: recursively sort

DR. NEEPA SHAH 108

Dr. Neepa Shah 54

Unit 4: Searching and Sorting

QUICK-SORT TREE

DR. NEEPA SHAH 109

IN-PLACE QUICK-SORT

 Divide step: l scans the sequence

from the left, and r from the right.
 A swap is performed when l is at
an element larger than the pivot
and r is at one smaller than the
pivot.

DR. NEEPA SHAH 110

Dr. Neepa Shah 55

Unit 4: Searching and Sorting

IN PLACE QUICK SORT (CONT’D)

A final swap with the pivot completes the divide step

DR. NEEPA SHAH

https://www.youtube.com/watch?v=-2VqW516BcI 111

EXAMPLE CONTD.

DR. NEEPA SHAH 112

Dr. Neepa Shah 56

Unit 4: Searching and Sorting

QUICK SORT PROCEDURE / ALGORITHM

1. If q-p > 1 do steps 2-5 (i.e. p < q)

2. Apply partition algorithm and
3. obtain pivot index m
4. Apply quick sort to {s0 … sm-1}
5. Apply quick sort to {sm+1 … sn-1}

DR. NEEPA SHAH 113

QUICK SORT PROCEDURE / ALGORITHM

void sort(int a[],int p, int q) {

if (q-p < 2)
{
return;
} Call from main
sort (a, 0, n-1)
int m = partition(a, p, q) ;
sort(a, p, m-1);
sort(a, m+1, q);
}

DR. NEEPA SHAH 114

Dr. Neepa Shah 57

Unit 4: Searching and Sorting

PARTITION ALGORITHM
int partition(int a[], int p, int q)
{

int pivot = a[p], i = p, j = q;

while (i < j)
{
while (i < j && a[--j] >= pivot) ;
if(i < j)
a[i] = a[j];

while (i < j && a[++i] <= pivot) ;

if(i < j)
a[j] = a[i];
}
a[j] = pivot;
DR. NEEPA SHAH 115
return j;
}

QUICKSORT – ANALYSIS

Worst Case: (assume that we are selecting the first element as pivot)
 The pivot divides the list of size n into two sub-lists of sizes 0 and n-1.
 The number of key comparisons
= n-1 + n-2 + ... + 1
= n2/2 – n/2 ➔ O(n2)
 So, Quicksort is O(n ) in worst case
2

Dr. Neepa Shah 58