Question

In a java program:

a) Given the following list of numbers:

90 8 7 56 123 235 9 1 653

trace the execution for:

Selection Sort (only the first 5 steps)

MergeSort.

(b) Given the following list of numbers:

3 1 4 1 5 9 2 6 5 3 5

trace the execution for quicksort with median-of-three partitioning and a cutoff of 3.

Answer 1

i)

arr=[90,8,7,56,123,235,9,1,653]

First 5 steps are

[1,90,8,7,56,123,235,9,653]

[1,7,90,8,56,123,235,9,653]

[1,7,8,90,56,123,235,9,653]

[1,7,8,9,90,56,123,235,653]

[1,7,8,9,56,90,123,235,653]

ii)

Merge sort steps are

[90,8,7,56,123,235,9,1,653]

[90,8,7,56,123] [235,9,1,653]

[90,8,7] [56,123] [235,9] [1,653]

[90,8] [7] [56] [123] [235] [9] [1] [653]

[90] [8] [7] [56] [123] [235] [9] [1] [653]

[8,90] [7] [56] [123] [235] [9] [1] [653]

[7,8,90] [56,123] [9,235] [1,653]

[7,8,56,90,123] [1,9,235,653]

[1,7,8,9,56,90,123,235,653]

Merge sort completed.