Given a list of seven single-digit integers of your UID (if the UID is longer, k

Question

Given a list of seven single-digit integers of your UID (if the UID is longer, keep its first seven digits), describe ordering the list with insertion sort in a table, similar by layout to Table 2.1 (Textbook). Your table should detail all six steps of sorting, including numbers of comparisons, C_i, and backward moves, M_t at each step i of sorting, as well as show the list after each step, i = 1, 2,...,6. Using the math induction, prove that the maximum and average numbers of inversions in a list [a_1,...,a_n] of integers a, are I_max:n = 1/2(n - 1)n and I_ave:n = 1/4(n - l)n, respectively. The base case I_max:2 = 1and I_ave:2 = 0.5 is for n = 2.

Explanation / Answer

Solution: Please follow these problems as shown in below

Program 1:

#include<stdio.h>

int main() {

   int i, j, num=6, temp, arr[20];

printf("Enter total elements: ");

   scanf("%d", &num);

printf("Enter %d elements: ", num);

   for (i = 0; i <=num; i++) {

      scanf("%d", &arr[i]);

   }

   for (i = 1; i <=num; i++) {

      temp = arr[i];

      j = i - 1;

      while ((temp < arr[j]) && (j >= 0)) {

         arr[j + 1] = arr[j];

         j = j - 1;

      }

      arr[j + 1] = temp;

   }

   printf("After Sorting: ");

   for (i = 0; i < num; i++) {

      printf("%d", arr[i]);

   }

   return 0;

}

Probelm 2:

Maximum number of inversions:

a) Prove by induction that the number of inversions is n(n1)/2.

1^0 If n=1, we have only one permutation which has no inversions.

2^0 Suppose the claim is true for nn elements. If we add (n+1)-th element, then we have inversions coming from the first n elements -- there is at most n(n1)/2 of them, and we also have inversions containing the (n+1)-th element -- there is at most n of them.n(n1)/2+n=n(n+1)/2

So we obtained the same formula for (n+1) instead if n.

b) Prove by induction that the permutation (n,n1,…,2,1)has exactly n(n1)/2 inversions.

(Note that I am using one-line notation, not cycle notation for permutations.)

1^0 The permutation (1) has no inversions.

2^0 The permutation (n+1,n,…,2,1) has nn inversions containing the element (n+1). The remaining inversion are the same as in the permutation (n,…,2,1).

So together we have n(n1)/2+n=n(n+1)/2

Average number of inversions:

(In the equation denoted by () we have the factor (n+1) since there are (n+1) possibilities how to obtain the same permutation from a permutation of (n+1) elements.)

The last equation yields

An+1 = n/2+An= n/2+n(n1)/4 = n(n+1)/2        (:n=2)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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