Bubble sort can be improved to run more efficiently when the

Bubble sort can be improved to run more efficiently when the input is nearly in order by testing whether no exchange at all are performed on one of the passes. a. Modify the algorithm so that it stops when no exchange are performed on one of the passes. b. Write a program to compare the actual running times of the original Bubble Sort and the modified algorithm. Your code should test the sorting methods for different size of N (10, 100, 1000, 4000, 8000, 10000, 25000, 50000, 75000 and 100000) and different types of data (sorted in ascending order, sorted in descending order, and unsorted). Your output should contain tables of the actual running time for each algorithm. c. Plot the obtained measured time as a function of the size of the input. Analyze your results. For each algorithm give your explanation on the results with the change of the input data. Which algorithm is the best and worst for each input data? d. implement a version of bubble sort that alternates left-to-right and right-to-left passes through the data. Compare its performance with your algorithms in (b).

Solution

Bubble sort can also be used efficiently on a list of any length that is nearly sorted (that is, the elements are not significantly out of place). For example, if any number of elements are out of place by only one position (e.g. 0123546789 and 1032547698), bubble sort\'s exchange will get them in order on the first pass, the second pass will find all elements in order, so the sort will take only 2n time. When the list is already sorted (best-case), the complexity of bubble sort is only O(n).

ans:c