C Programming only.

Please fill in the missing code in the THREE designated areas in source file Problem37.c that says "Student provides missing code......" below.

ALL Necessary source files located below.

PLEASE also provide screenshot of the compiled output once complete. I have provided a sample one which should give an idea on how it should look.

Problem

Allow the user to input n, the number of integers in the dynamically-allocated array A[]. Randomly choose the contents of A[] from the interval [ 1,10*n ], use the int-returning function NumberOfInversions() to display the number of inversions in A[], use the void-returning function DoComparisonCountingSort() to sort the contents of A[], then display the number of compares required to sort the contents of A[] in ascending order. Hint The algorithm for the Comparison Counting Sort can be found in Exercise 1 at the end of Section 1.3 on page 23 of third edition our text book.

//--------------------------------------------------

// Problem #37

// Problem37.c

//--------------------------------------------------

#include

#include

#include

#include

#include "..\Random.h"

#define DISPLAYARRAY

//--------------------------------------------------

int main()

//--------------------------------------------------

{

void BuildRandomArray(int A[],int n);

int MaximumInversions(int n);

int NumberOfInversions(int A[],int n);

void DisplayArraySlice(char label[],int A[],int n,int L,int R);

void DoComparisonCountingSort(/*IO*/int A[],/*IN*/int n,/*OUT*/int *numberCompares);

int n;

SetRandomSeed();

printf("n? ");

while ( scanf("%d",&n) != EOF )

{

int *A = (int *) malloc(sizeof(int)*n);

int numberCompares;

BuildRandomArray(A,n);

#ifdef DISPLAYARRAY

DisplayArraySlice("UNSORTED",A,n,0,n-1);

#endif

printf("# of inversions is %10d (%.1f%% of %d) ",

NumberOfInversions(A,n),

100*((double) NumberOfInversions(A,n)/MaximumInversions(n)),

MaximumInversions(n));

DoComparisonCountingSort(A,n,&numberCompares);

printf("# of compares is %10d ",numberCompares);

#ifdef DISPLAYARRAY

DisplayArraySlice(" SORTED",A,n,0,n-1);

#endif

free(A);

printf(" n? ");

}

system("PAUSE");

return( 0 );

}

//--------------------------------------------------

void BuildRandomArray(int A[],int n)

//--------------------------------------------------

{

int i;

for (i = 0; i

A[i] = RandomInteger(1,10*n);

}

//--------------------------------------------------

void DisplayArraySlice(char label[],int A[],int n,int L,int R)

//--------------------------------------------------

{

const int WIDTH = (int) ceil(log10(10*n));

int i;

printf("%s",label);

if ( !(L

printf(" (empty) ");

else

{

for (i = 0; i

if ( (L

printf("%*d",WIDTH+1,A[i]);

else

{

char formatString[4+1];

sprintf(formatString,"%%%dc",WIDTH);

printf(formatString,' ');

}

printf(" ");

}

}

//--------------------------------------------------

int MaximumInversions(int n)

//--------------------------------------------------

{

Student provides missing code to compute the number of combinations of the n elements

taken 2 at a time, that is, C(n,2).

}

//--------------------------------------------------

int NumberOfInversions(int A[],int n)

//--------------------------------------------------

{

Student provides missing code to consider every combination of the n elements of

A[] taken 2 at a time in order to count the number of combinations that are inversions.

}

//--------------------------------------------------

void DoComparisonCountingSort(/*IO*/int A[],/*IN*/int n,/*OUT*/int *numberCompares)

//--------------------------------------------------

{

int i,j;

int *count = (int *) malloc(sizeof(int)*n);

int *S = (int *) malloc(sizeof(int)*n);

*numberCompares = 0;

Student provides missing code to implement a slightly modified version of the

ComparisonCountingSort algorithm found in Exercises 1.3 Problem #1 on page 23 of our text book.

free(count);

free(S);

}

//--------------------------------------------------

// Random.h

//--------------------------------------------------

#ifndef RANDOM_H

#define RANDOM_H

#include

// initialize the "seed" used by the "rand()" function in

void SetRandomSeed(void);

// return uniformly, randomly chosen integer from [ LB,UB ]

int RandomInteger(int LB,int UB);

// return uniformly, randomly real number chosen from [ 0.0,1.0 )

double RandomReal(void);

// return randomly-chosen boolean with bias from { false,true }

bool RandomBoolean(double bias);

// return uniformly, randomly-chosen character from characters[i], i in [ 0,(size-1) ]

char RandomCharacter(char characters[],int size);

#endif

/--------------------------------------------------

// Random.c

//--------------------------------------------------

#include

#include

#include

#include

#include ".\Random.h"

//--------------------------------------------------

void SetRandomSeed(void)

//--------------------------------------------------

{

srand(time(NULL));

}

//--------------------------------------------------

int RandomInteger(int LB,int UB)

//--------------------------------------------------

{

return( (int) (RandomReal()*(UB-LB+1)) + LB );

}

//--------------------------------------------------

double RandomReal()

//--------------------------------------------------

{

int R;

do

R = rand();

while ( R == RAND_MAX );

return( (double) R/RAND_MAX );

}

//--------------------------------------------------

bool RandomBoolean(double bias)

//--------------------------------------------------

{

return( RandomReal()

}

//--------------------------------------------------

char RandomCharacter(char characters[],int size)

//--------------------------------------------------

{

return( characters[RandomInteger(0,(size-1))] );

}

ample Program Dialog (with macro DISPLAYARRAY defined n? 10 UNSORTED 88 33 35 84 16 90 99 17 572 # of inve rsions is # of compare sis 26 (57.8% of 45) 45 SORTED 2 16 1733 35 57 84 88 90 99 n? 20 UNSORTED 187 58 104 136 200 15 191 171 86 131 73 193 158 81 179 44 198 98 171 142 92 (48.4% of 190) 190 # of compare sis SORTED 15 445873 81 86 98 104 131 136 142 158 171 171 179 187 191 193 198 200 Sample Program Dialog (with macro DISPLAYARRAY not defined n? 10 # of inversions is # of compare sis 34 (75.6% of 45) 45 n? 100 # of inve r sions is # of compares is 2710 (54.7% of 4950) 4950 n? 1000 # of inve r s ions is # of compare sis 245295 (49.1% of 499500) 499500 n? 10000 # of inversions is 24981974 (50.0% of 49995000) # of compares is 49995000 WHAT in the world does this mean?! Why did it happen?! HoW can you fix it?! n? 100000 # of inversions is -1797829808 (-255.0% of 704982704) #of compares is 704982704