13 25 40 20 28 48 19 14
Complete the following:
a) Use the bubble sort (page 214) to sort the values showing theorder of the values in the list after every pass of the sortingalgorithm.
b) What is the time complexity of the sort (use the number ofcomparisons required as a measure of time.)
c) Modify the algorithm so it stops if there are no swaps in acomplete pass. How many comparisons would be needed in yourspecific example?
d) Choose one of the following properties of Algorithms and showthat the bubble sort has the given property:
Input: an algorithm has input values;
Output: from each set of input values an algorithm producesoutput values that are a solution to the problem;
Definiteness: the steps in an algorithm must be preciselydefined;
Correctness: an algorithm must produce the correct output valuesfor each set of input values;
Finiteness: an algorithm should produce the output after afinite number of steps;
Effectiveness: it must be possible to perform each step in thealgorithm in a finite amount of time;
Generality: the algorithm must be applicable to a category ofproblems, not a single set of input values
