Question

An online/anytime sorting algorithm is one that reads its input numbers one at a time, and...

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 3rd 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[___________]<A[___________]

8                          swap ________ and _________

                   else

9                          exit the for loop

11 return A

Homework Answers

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
# data structure Recall that the Insertion sort algorithm (for sorting an array A) from low...
# data structure Recall that the Insertion sort algorithm (for sorting an array A) from low to high has the skeleton form: for (i = 1; i < A.length; i++) { details omitted } For i = 1 to 6, show how the contents of the array is rearranged if at all) after each iteration of the for-loop. (10 pts) the original array A                                            A 6. 4. 7. 5....
Complete the java code as per the comments public class Sorting {    ///////////////////////////////////////////////    //...
Complete the java code as per the comments public class Sorting {    ///////////////////////////////////////////////    // STEP 1 -- Make sorting methods generic    ///////////////////////////////////////////////       /**    * Re-orders the contents given array using the insertion sort algorithm.    *    * @param data The array to be sorted.    */    //TODO: Make me generic to work on any kind of Comparable data!    public static void insertionSort(int[] data)    {        int insert; // temporary...
in C++ Please and thanks Here is a list of 6 numbers. Use the selection sort...
in C++ Please and thanks Here is a list of 6 numbers. Use the selection sort algorithm to sort this list. Fill in this table with each iteration of the loop in the selection sort algorithm. Mark the place from which you are looking for the 'next smallest element'. In this display, the upper numbers are the indices, the lower numbers are in the corresponding positions. Use the several rows provided to show the sequence of steps. 0 1 2...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
In JAVA Find the code for sorts in your language some where online. You will copy...
In JAVA Find the code for sorts in your language some where online. You will copy code from the internet (with citation!) and modify it to test. Make a random array of integers, then perform each search on them. LINEAR SEARCH Write a linear search method to find a number in the list. Call this before each of your sort methods. Include a comment explaining how Linear Search works, when to use it, when you cannot. BINARY SEARCH Write a...
The following algorithm finds the initial substring of y that can be reversed and found in...
The following algorithm finds the initial substring of y that can be reversed and found in y. For example, longestInitialReverseSubstringLength(“aabaa”) = 5, because “aabaa” is the same string forwards and backwards, so the longest initial substring that can be reversed and found in the string is “aabaa”. Also, longestInitialReverseSubstringLength(“bbbbababbabbbbb”) is 6, because “babbbb” can be found in the string (see color-highlighted portions of the string), but no longer initial string exists reversed in any part of the string. longestInitialReverseSubstringLength(String y)...
Topics Arrays Accessing Arrays Description Write a C++ program that will display a number of statistics...
Topics Arrays Accessing Arrays Description Write a C++ program that will display a number of statistics relating to data supplied by the user. The program will ask the user to enter the number of items making up the data. It will then ask the user to enter data items one by one. It will store the data items in a double array. Then it will perform a number of statistical operations on the data. Finally, it will display a report...
Assignment #4 – Student Ranking : In this assignment you are going to write a program...
Assignment #4 – Student Ranking : In this assignment you are going to write a program that ask user number of students in a class and their names. Number of students are limited to 100 maximum. Then, it will ask for 3 test scores of each student. The program will calculate the average of test scores for each student and display with their names. Then, it will sort the averages in descending order and display the sorted list with students’...
Curve-Fit Function USING MATLAB Using the top-down design approach, develop a MATLAB function A8P2RAlastname.m that reads...
Curve-Fit Function USING MATLAB Using the top-down design approach, develop a MATLAB function A8P2RAlastname.m that reads data from a file and performs regression analysis using polyfit and polyval. The function shall have the following features: The input arguments shall include the file name (string), a vector of integers for the degrees of polynomial fits to be determined, and an optional plot type specifier (‘m’ for multiple plots, ‘s’ for a single plot - default). The data files will be text...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT