a. Trace the operation of insertion sort algorithm when sorting the array A[7] (

Question

a. Trace the operation of insertion sort algorithm when sorting the array A[7] (5, 6. 2, 7.9, 4, 3). Please fill the table to show the changes of the array A after each iteration. The first column is filled. void Insertionsort (int AC], int size) for (int i 1; i size i++) int J i; while (J 0 66 A 11 ACJ]) temp Atj temp: b. Please analyze the number of comparisons and the number of swaps required in the worst case (the key of items in the amay are arranged from the highest to the lowest) and the best case (the key of items in the array are arranged from the lowest to the lowest highest), when using the insertion sort algorithm to sort all items in an array with n items. of comparisons Bof swaps the worst case the case c. Please present a way to improve the algorithm's efficiency by reducing the number of comparisons in the worst case and average case (we know nothing about the arrangement of the key in the array). d. Please show if the insertion sort is stable. How many auxiliary memory spaces are required during the insertion sort algorithm?

Explanation / Answer

There needs to be modification in program

while swapping, the current program puts value of a[j] in temp and a[j-1] then no point swapping as at end a[j-1] and a[j] both will hold a[j] value.

so modification is

temp = a[j-1]

i j j>0 a[j-1]>a[j] temp=a[j-1] a[j-1]=a[j] a[j]=temp j-- array 1 1 TRUE 5>6, false NA NA NA NA 5,6,2,7,9,4,3 2 2 TRUE 6>2, TRUe temp = 6 a[1] = 2 a[2]= 6 1 5,2,6,7,9,4,3 1 TRUE 5>2 True temp= 5 a[0]=2 a[1]=5 0 2,5,6,7,9,4,3 0 FALSE 3 3 TRUE 6>7, False NA NA NA NA 2,5,6,7,9,4,3 4 4 TRUE 7>9, False NA NA NA NA 2,5,6,7,9,4,3 5 5 TRUE 9>4, True temp =9 a[4] = 4 a[5] = 9 4 2,5,6,7,4,9,3 4 TRUE 7>4, True temp =7 a[3] = 4 a[4] = 7 3 2,5,6,4,7,9,3 3 TRUE 6>4, True temp = 6 a[2] = 4 a[3] = 6 2 2,5,4,6,7,9,3 2 TRUE 5>4,True temp = 5 a[1]=4 a[2]= 5 1 2,4,5,6,7,9,3 1 TRUE 2>4,FALSE NA NA NA NA 6 6 TRUE 9>3,True temp = 9 a[5] = 3 a[6] = 9 5 2,4,5,6,7,3,9 5 TRUE 7>3, True temp = 7 a[4] = 3 a[5] =7 4 2,4,5,6,3,7,9 4 TRUE 6>3, True temp = 6 a[3]= 3 a[4] = 6 3 2,4,5,3,6,7,9 3 TRUE 5>3, True temp = 5 a[2] =3 a[3] = 5 2 2,4,3,5,6,7,9 2 TRUE 4>3, True temp = 4 a[1]= 3 a[2]= 4 1 2,3,4,5,6,7,9 1 TRUE 2>3, False NA NA NA NA

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.