1) Trace the action of the algorithm with the following input: -65 -71 -86 -58 -
ID: 3902401 • Letter: 1
Question
1) Trace the action of the algorithm with the following input: -65 -71 -86 -58 -60 -99
2)How many comparisons does it make? How many swaps in the array? How much space does it take? Give answers as exact as you can, then also provide the asymptotic bound (big-Oh notation)
3) Is Insertion Sort a stable search? Explain your reasoning.
Here is the pseudocode for Insertion Sort procedure InsertionSort (A: array) is begin i, j, v: integer for i in 2.. N loop while al j-1>v loop end loop end loop end InsertionSortExplanation / Answer
Assuming the '-' operator is a separator to the numbers, else if it's negative sign, the logic is simply reversed.
1) Trace of algorithm run:
65
65 , 71 (No change as the elements are already in ascending order)
65 , 71 , 86
65 , 71 , 86 , 58 => 65 , 71 , 58 , 86 => 65 , 58 , 71 , 86 => 58 , 65 , 71 , 86
58 , 65 , 71 , 86 , 60 => 58 , 65 , 71 , 60 , 86 => 58 , 65 , 60 , 71 , 86 => 58 , 60 , 65 , 71 , 86
58 , 60 , 65 , 71 , 86 , 99 (No interchange)
2) This implies:
Each step whether order modification happends or not performs an additional interchange apart from the number of interchanges. Hence the total number of comparisons made are: 1+2+3+4+5+1=16
As in worst case, if the array is already in descending order, the entire array will be reversed and every value will shift to (n - (it's current location)). And this sum is quite known to be of order O(n^2)
Total number of swaps are highlighted in bold = 6 (This is worst case will also be O(n^2)
It takes a space of full array size + 3 variables (v ,i , j) = 'n' (size of array) => O(n)
3) Indeed the insertion sort is stable, as the keys will equal value never gets comapred and hence are never swapped. This renders their orignal relative position to be same even after the sorting.
Hope this helps!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.