Problem 13
Suppose selection sort and bubble sort are both performed on a list that is already sorted. Does bubble sort do fewer exchanges than seloction sort? Explain.
Problem 14
Bubble sort can be improved. Smart bubble sort keeps track of how many exchanges are done within any single poss through the unsorted section of the list. If no ewchanges occur, then the list is sorted and the algorithm should stop. a. Write a pseudocode version of the smart bubble sort algorithm. b. Perform a smart bubble sort on the following list. How many comparisons are required? \(7,4,12,9,11\) c. Describe the best-case scenario for smart bubble sort on an n-element list. How many comparisons are required? How many exchanges are required? d. Under what circumstances does smart bubble sort do the same number of comparisons as regular bubble sort?
Problem 15
Show the steps in merging \(A\) and \(B\) into \(C\) where $$ A=8,12,19,34 \quad B=3,5,15,21 $$
Problem 16
Use mergosort to sort the list \(6,3,1,9\). Count the total number-of comparisons, including
Problem 19
Agorithms A and B porfom the same tardk. Cn inpur of s coe n, sigorithm A cwocutes 0.003 \(m^{2}\) instructions, and algorithm B expcutes 243 n inetructions. Find the approwimate value of \(n\) above ahich algorithm \(B\) is mono efficient. Prou may use a calculator or spreadsheet.
Problem 20
Suppose a metropolitan area is divided into four school restricts: \(1,2,3,4\). The Seate Beard af Etupcation beeppos tack of the number of student transfers fram ane district ted ancether and the shudent transiers within a district. This information is nesorded each year in a \(4 x\) table ss shown here. The entry in row 1 , cohimn \(3 \mid 314\), for exsmple, stiows the number of student tronefers trom district 1 to district 3 for the yeary the entry in now 1 , wien w.column \(1(243)\) shows the number of student transfers within district 1 . \begin{tabular}{l|llll} & 1 & 2 & 3 & 4 \\ \hline 1 & 243 & 187 & 314 & 244 \\ 2 & 215 & 420 & 345 & 172 \\ 3 & 197 & 352 & 385 & 261 \\ 4 & 340 & 135 & 217 & 344 \end{tabular} Suppose there are \(n\) school districts, and the Board of Education maintains an \(n \times n\) table. a. Write a pseudocode algorithm to print the table, that is, to print each of the entries in the table. Write an expression for the number of print statements the algorithm executes. b. Write a pseudocode algorithm to print \(n\) copies of the table, one to give to each of the \(n\) school district supervisors. Write an expression for the number of print statements the algorithm executes. c. What is the order of magnitude of the work done by the algorithm in part \(b\) if the unit of work is printing a table element?
Problem 21
Write the data list that results from running the shuffle-left algorithm to clean up the following data. Find the exact number of copies done. \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|} \hline 3 & 0 & 0 & 2 & 6 & 7 & 0 & 0 & 5 & 1 \\ \hline \end{tabular}
Problem 25
Consider the following sorted list of names. Arturo, Elsa, JoAnn, John, José, Lee, Snyder, Tracy a. Use binary search to decide whether Elsa is in this list. What names will be compared with Elsa? b. Use binary search to decide whether Tracy is in this list. What names will be compared with Tracy? c. Use binary search to decide whether Emile is in this list. What names will be compared with Emile?
Problem 26
Use the binary search algorithm to decide whether 35 is in the following list: \(3,6,7,9,12,14,18,21,22,31,43\) What numbers will be compared with 35 ?
Problem 27
If a list is already sorted in ascending order, a modified sequential search algorithm can be used that compares against each element in turn, stopping if a list element exceeds the target value. Write a pseudocode version of this short sequential search algorithm.
