Exercise 1: [10 marks]

Given the following list of numbers in an array:

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 25

10

30

8

11

100

65

17

20

37

If you are asked to sort the array using the Selection Sort algorithm (given ascending order), what would be the contents of the array after each of the first three passes of compare and sort. Fix the smaller items first. Pass1

A) What is the total number of comparisons necessary to complete the first pass through the list?

B) What is the total number of comparisons necessary to complete the third pass through the list?

C) How many passes will it take to sort the entire list?

D) How many comparisons will it take to sort the entire list?

E) To verify your answer to part (D) above, start the Sorting applet and choose the Selection Sort. In the text area remove the current text ("Your data set goes here") and type in the above new set of 10 numbers. Press return after every number. Take a screenshot.

F) Does the applet justify your answer to part (D)?