9. Understanding and modifying algorithms: Online/Anytime Sorting (10 points)

An online/anytime sorting algorithm is one that reads its input numbers one at a time, and maintains a sorted array of all the inputs it has seen so far, so that if it is interrupted at any time, it will still output the correct answer for the inputs that it has processed. Not all sorting algorithms are amenable to modification to make them anytime. But one sorting algorithm, Bubble Sort, is easy to so modify.

First, understand the ascending order Bubble Sort algorithm below:

Bubble-sort (A: Array [1...n] of number)

1 for i=1 to (n-1)

2 for j=1 to (n-i)

3 if A[j]>A[j+1] then

4 temp=A[j]

5 A[j]=A[j+1]

6 A[j+1]=temp

(4 points) If input A=[12,5,11,6,10,7,9,8], what will A be after the 3^rd iteration of the outermost for loop of the Bubble-sort algorithm completes? A=[__, __, __, __, __, __, __, __]

(6 points) Modify the algorithm above to obtain an online/anytime sorting algorithm. Assume that quit is a global Boolean that is set external to the algorithm indicating that it should terminate. Some parts are given. Fill in the blanks:

Anytime-Bubble-Sort ()

Let A be an empty dynamic (variable length) array with a large enough capacity

1 array-length=0

2 if quit is false

3 next= read next number from the input stream

4 array-length= array-length+1

5 A[array-length]=next

6 for j=___________ down to _________

7 if A[___________]

8 swap ________ and _________

else

9 exit the for loop

11 return A