Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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.

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.

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.

image text in transcribed

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

// 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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database And Expert Systems Applications 24th International Conference Dexa 2013 Prague Czech Republic August 2013 Proceedings Part 2 Lncs 8056

Authors: Hendrik Decker ,Lenka Lhotska ,Sebastian Link ,Josef Basl ,A Min Tjoa

2013th Edition

3642401724, 978-3642401725

Students also viewed these Databases questions

Question

5-8 What are the advantages and disadvantages of the BYOD movement?

Answered: 1 week ago