IIT Bombay

(1)

IIT Bombay

Computer Programming

Dr. Deepak B Phatak Dr. Supratik Chakraborty

Department of Computer Science and Engineering

IIT Bombay

(2)

IIT Bombay

• The sorting problem

• Selection sort

• Intuition

• C++ implementation

• Analysis of performance

2 Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay

Quick Recap of Relevant Topics

(3)

IIT Bombay

• Merge sort

• Intuition

• Animated example

Overview of This Lecture

(4)

IIT Bombay

Recall: Intuition Behind Selection Sort

Solve part of the problem

Arrive at a similar but

“simpler” problem to solve:

Sort remaining marks

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 4

24 18 17 25 27 24 1

1 27

Get only the first

element in its right place

18

17

25

24

(5)

IIT Bombay

A General Paradigm In Computing

• Decompose a larger problem into smaller sub-problems

• Solve each sub-problem separately

Often using same techniques as used to address the larger problem

• Combine results of sub-problems to obtain solution of larger

problem

(6)

IIT Bombay

Sorting by Divide-and-Conquer

24 18 17 25 27 24

24 18 17 25 27 24 Divide

Sort first half of array

(7)

IIT Bombay

Sorting by Divide-and-Conquer

24 18 17 25 27

24 18 17 25 27 Divide

24 18 17

Sort 24

18

17

(8)

IIT Bombay

Sorting by Divide-and-Conquer

24 18 17 25 27 24

24 18 17 25 27 24 Divide

24 18 17 27 25 24 Sort

Sort

Merge

27

25

24

18

17

(9)

IIT Bombay

What Were The Steps?

• Divide an array of size n into two sub-arrays of size  n/2

• Sub-array sizes may differ by 1 if n is odd

• Easy!

• Sort each sub-array of size n/2

• Hmm … how?

• Selection sort ???

• Merge sorted sub-arrays, each of size n/2

Wait for a

few slides !!!

(10)

IIT Bombay

Merging Sorted Sub-arrays

24 18 17 27 25 24 27 25 24

24 18 17

27 > 24

Sorted

Sub-array1

Sorted

Sub-array2

(11)

IIT Bombay

Merging Sorted Sub-arrays

24 18 17 27 24 18 17

25 > 24

Sorted 27

Sub-array1

Sorted

(12)

IIT Bombay

Merging Sorted Sub-arrays

24 18 17 27 25 24 27 25 24

24 18 17

24 > 24

27 25 Sorted

Sub-array1

Sorted

Sub-array2

(13)

IIT Bombay

Merging Sorted Sub-arrays

24 18 17 27 27 24 18 17

24 > 18

27 25 24 Sorted

Sub-array1

Sorted

(14)

IIT Bombay

Merging Sorted Sub-arrays

24 18 17 27 25 24 27 25 24

24 18 17 Sorted

Sub-array1

Sorted

Sub-array2

27 over

25

24

(15)

IIT Bombay

Merging Sorted Sub-arrays

24 18 17 27 27 24 18 17 Sorted

Sub-array1

Sorted

Sub-array2

27 over

25

24

18

(16)

IIT Bombay

Merging Sorted Sub-arrays

24 18 17 27 25 24 27 25 24

24 18 17 Sorted

Sub-array1

Sorted

Sub-array2

24 18 24 27 25 24 24 18 17

Both sorted sub-arrays

over

Merged sorted array

(17)

IIT Bombay

What Were The Steps?

• Divide an array of size n (assume n is even) into two sub- arrays of size n/2

• Easy!

• Sort each sub-array of size n/2

• Hmm … how?

• Selection sort ???

• Merge sorted sub-arrays, each of size n/2

We were trying to sort an array

of size n

(18)

IIT Bombay

What Were The Steps?

• Divide an array of size n (assume n is even) into two sub- arrays of size n/2

• Easy!

• Sort each sub-array of size n/2

• Hmm … how?

• Selection sort ???

• Merge sorted sub-arrays, each of size n/2

• Hmm … how?

Why not try the same steps

on each sub-

array?

(19)

IIT Bombay

What Were The Steps?

• Divide an array of size n (assume n is even) into two sub- arrays of size n/2

• Easy!

• Sort each sub-array of size n/2

• Hmm … how?

• Selection sort ???

• Merge sorted sub-arrays, each of size n/2

Recursively sort each sub- array by same

method

Termination case of recursion:

(20)

IIT Bombay

Divide-and-Conquer In Action

24 18 17 25 27 24

24 18 17 25 27 24 Divide

Divide-and-Conquer In Action

24 18 17 25 27

24

18 Divide 17

(22)

IIT Bombay

Divide-and-Conquer In Action

24 18 17 25 27 24

24 18 17

25 27 24

24 18 17

Termination case

17 Divide-and-Conquer In Action

24 18 17 25 27

24 18 17

25 27

24 18 17

18 Divide

(24)

IIT Bombay

Divide-and-Conquer In Action

24 18 17 25 27 24

24 18 17

25 27 24

24 18 17

18 17

Termination case

(25)

IIT Bombay

Divide-and-Conquer In Action

24 18 17

Termination case 24

18 17 25 27

24 18 17

18 17 25

27

(26)

IIT Bombay

Divide-and-Conquer In Action

25 27 24

24 18 17 Merge

24 18 17 25 27 24

24 18 17

18

17

(27)

IIT Bombay

Divide-and-Conquer In Action

25 27 24 24

18 17 25 27

24 18 17

18

17

(28)

IIT Bombay

Divide-and-Conquer In Action

25 27 24

24 18 Merge 17

24 18 17 25 27 24

24

18

17

(29)

IIT Bombay

Divide-and-Conquer In Action

24 18 17 25 27 24

18

17

25

27

(30)

IIT Bombay

Divide-and-Conquer In Action

24 18 17 25 27 24

25 27 24 Divide

24

18

17

25

27

24

(31)

IIT Bombay

Divide-and-Conquer In Action

24 18 17

25 27

25 Termination case

24

18

17

25

27

(32)

IIT Bombay

Divide-and-Conquer In Action

24 18 17

25 27 24

24 27 Divide

24 18 17 25 27 24

25

27

24

(33)

IIT Bombay

Divide-and-Conquer In Action

24 18 17

25

27 Termination case 25

27 24

18

17

25

27

(34)

IIT Bombay

Divide-and-Conquer In Action

24 18 17

25 24 27

Termination case 24

18 17 25 27 24

25 27 24

27

24

(35)

IIT Bombay

Merge

Divide-and-Conquer In Action

24 18 17

25 27 24

18 17 25 27

25

27

(36)

IIT Bombay

Divide-and-Conquer In Action

24 18 17

25 24

18 17 25 27 24

25 27 24

27

24

(37)

IIT Bombay

Divide-and-Conquer In Action

24 18 17

25 Merge

24 18 17 25 27

25

27

(38)

IIT Bombay

Divide-and-Conquer In Action

24 18 17 27 25 24 24

18

17

25

27

24

(39)

IIT Bombay

Divide-and-Conquer In Action

24 18 17 27 25 Merge

24

18

17

25

27

(40)

IIT Bombay

Divide-and-Conquer In Action

27 25 24 24 18 17

Sorted array !!!

(41)

IIT Bombay

Merge Sort

24 18 17 25 27

27 25 24 24 18

MERGE SORT

(42)

IIT Bombay

IIT Bombay

Computer Programming

Dr. Deepak B Phatak Dr. Supratik Chakraborty

Department of Computer Science and Engineering

IIT Bombay

• The sorting problem

• Selection sort

• Intuition

• C++ implementation

• Analysis of performance

Quick Recap of Relevant Topics

• Merge sort

• Intuition

• Animated example

Overview of This Lecture

Recall: Intuition Behind Selection Sort

Solve part of the problem

Arrive at a similar but

“simpler” problem to solve:

Sort remaining marks

24 18 17 25 27 24 1

1 27

Get only the first

element in its right place

18

17

25

24

24

A General Paradigm In Computing

• Decompose a larger problem into smaller sub-problems

• Solve each sub-problem separately

Often using same techniques as used to address the larger problem

• Combine results of sub-problems to obtain solution of larger

problem

Sorting by Divide-and-Conquer

24 18 17 25 27 24

24 18 17 25 27 24 Divide

Similar but simpler problem Sort second half of array Similar but simpler problem

Sort first half of array

Sorting by Divide-and-Conquer

24 18 17 25 27

24 18 17 25 27 Divide

Similar but simpler problem Sort second half of array

24 18 17

Sort 24

18

17

Sorting by Divide-and-Conquer

24 18 17 25 27 24

24 18 17 25 27 24 Divide

24 18 17 27 25 24 Sort

Sort

Merge

27

25

24

24

18

17

What Were The Steps?

• Divide an array of size n into two sub-arrays of size  n/2

• Sub-array sizes may differ by 1 if n is odd

• Easy!

• Sort each sub-array of size n/2

• Hmm … how?

• Selection sort ???

• Merge sorted sub-arrays, each of size n/2

Wait for a

few slides !!!

Merging Sorted Sub-arrays

24 18 17 27 25 24 27 25 24

24 18 17

27 > 24

Sorted

Sub-array1

Sorted

Sub-array2

Merging Sorted Sub-arrays

24 18 17 27 24 18 17