c. Please present a way to improve the algorithm’s efficiency by reducing the nu

Question

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?

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 All, int size) for (int i 1 i size; i++) int j i; while (j 0 & & A[j 1] A[j]) tempo A[j] AIj 1] A j] tempo b. Please analyze the number of comparisons and the number of swaps required in the worst case (the key of items in the array 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 a items in an array with n items. of comparisons of swaps the worst case the best case

Explanation / Answer

(a)

After 1 iteration: 5 6 2 7 9 4 3
After 2 iteration: 2 5 6 7 9 4 3
After 3 iteration: 2 5 6 7 9 4 3
After 4 iteration: 2 5 6 7 9 4 3
After 5 iteration: 2 4 5 6 7 9 3
After 6 iteration: 2 3 4 5 6 7 9

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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