3. (5 points) Bubblesort can be described as follows: Consider sorting (in increasing order) n numbers...

  

Transcribed Image Text:

3. (5 points) Bubblesort can be described as follows: Consider sorting (in increasing order) n numbers by comparing the 1st and 2nd number and swapping them if they are out of order, then comparing the 2nd and 3rd number and swapping them if necessary, . . ., comparing the (n-1) st and nth number and swapping them if necessary. Then do this again for n-1 numbers, then n-2 numbers, etc. When no exchanges are required on some pass, the file is sorted. A different version of bubble sort keeps track of where the last swap occurred, and on the next pass, it will not go past this point. If the last change was made in the swap of locations i and i + 1, the next pass will not look at any elements past location i. 3a) Write iterative pseudocode for this new version of Bubblesort. 3b) Write a short paragraph that explains exactly why this new version of bubble sort will work. 3c) How does this new version of bubble sort does change the worst-case runtime analysis? Can you state what particular input will give worst-case runtime? Give a detailed explanation of what is involved in calculating the worst-case runtime analysis. 3. (5 points) Bubblesort can be described as follows: Consider sorting (in increasing order) n numbers by comparing the 1st and 2nd number and swapping them if they are out of order, then comparing the 2nd and 3rd number and swapping them if necessary, . . ., comparing the (n-1) st and nth number and swapping them if necessary. Then do this again for n-1 numbers, then n-2 numbers, etc. When no exchanges are required on some pass, the file is sorted. A different version of bubble sort keeps track of where the last swap occurred, and on the next pass, it will not go past this point. If the last change was made in the swap of locations i and i + 1, the next pass will not look at any elements past location i. 3a) Write iterative pseudocode for this new version of Bubblesort. 3b) Write a short paragraph that explains exactly why this new version of bubble sort will work. 3c) How does this new version of bubble sort does change the worst-case runtime analysis? Can you state what particular input will give worst-case runtime? Give a detailed explanation of what is involved in calculating the worst-case runtime analysis.