PLEASE PROVIDE EXPLANATION Suppose that you want to sort an array into ascending

Question

PLEASE PROVIDE EXPLANATION

Suppose that you want to sort an array into ascending order using insertion sort. It contains the integers 0 through n in some order, Where n is even. That means it contains n+1 integers!) Give the simplest possible exact answers, in terms of n, o each of the following questions. Express y answer as a simplified polynomial in n, not as a summation. Doing this will require careful counting followed by algebraic simplification. Justify your answers without appealing to the results of running a program. Comparisons" refer to comparisons of the numbers being sorted, not to other comparisons such as of array in that in each case, the array has an odd length It begins with zero, which is followed by a permutation of the integers 1 through n Please note f the array begins with 0 and the rest of the numbers are arranged into descending order, how many comparisons are required (For n 8, the array would be [0,8,7,6,5,4,3,2,1].) 2. If the array begins with 0, followed by the largest remaining odd and even integers, followed by the new largest remaining odd and even integers, and so on, how many comparisons are required? (For n 8, the array would be [0,7,8,5,6,3,4,1,2] 3. If the array begins with 0, followed by the odd numbers in descending order, followed by the remaining even numbers in de order, how many comparisons are required? (For n 8, the array would be [0,7,5,3,1,8,6,4, 22].)

Explanation / Answer

1. {0,8,7,6,5,4,3,2,1}
to sort in ascending order , start from 2nd element of array to last element.
8 will be compaired with 0 and it will not exchange because 8 is more than 0 .
now 7 will be compaired with 8 , here 8>7 than 8 and 7 will be exchanged and than 7 will be compaired with 0 where 0<7 so compairision will be stop.
now repeat for all the remaining nodes.
at the end, all the element will be sorted.

n(n+1)/2 compairision
8*9/2=36

2.{0,7,8,5,6,3,4,1,2}
here for even number , last compairision will be with the odd number before that , which is 1 less than that. so that all even number will not be compaired with the 0 so that 4 compairision will be saved.
so that compairision= 36-4=32

3.{0,7,5,3,1,8,6,4,2}
Here first all odd number will be compaired than even number.
all odd number will compaired till 0. even number will be stop when they got less number that.
so that total number of compairision = 1+2+3+4+1+3+5+7=26

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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