Question

. 36 1 2 31 44 1 1 9

Complete the following:

a) Use the bubble sort (page 214) to sort the values showing the order of the values in the list after every pass of the sorting algorithm.

b) What is the time complexity of the sort (use the number of comparisons required as a measure of time.)   

c) Modify the algorithm so it stops if there are no swaps in a complete pass. How many comparisons would be needed in your specific example?

d) Choose one of the following properties of Algorithms and show that the bubble sort has the given property:

• Input: an algorithm has input values;

• Output: from each set of input values an algorithm produces output values that are a solution to the problem;

• Definiteness: the steps in an algorithm must be precisely defined;

• Correctness: an algorithm must produce the correct output values for each set of input values;

• Finiteness: an algorithm should produce the output after a finite number of steps;

• Effectiveness: it must be possible to perform each step in the algorithm in a finite amount of time;

• Generality: the algorithm must be applicable to a category of problems, not a single set of input values.

Answer 1