C Programming

Take screenshot of compiled output once complete. (which should look similar to the sample one provided).

Fill in the missing code in the four areas that say "Student provides missing code..."

All source files Problem5.c, Random.h, Random.c located below.

Please make sure to provide all completed source code and screenshot of compiled output.

-will rate positively.

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

// Problem #5

// Problem5.c

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

#include

#include

#include

#include

#include "..\Random.h"

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

int main()

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

{

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

void CopyArray(int copyA[],const int A[],const int n);

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

int NumberOfInversions(const int A[],const int n,bool (*AreInverted)(const int LHS,const int RHS));

void DoBubbleSort(int A[],const int n,

bool (*ShouldSwap)(const int LHS,const int RHS),

int *numberCompares,

int *numberMoves);

void DoSelectionSort(int *A,const int n,

bool (*ShouldSelect)(const int LHS,const int RHS),

int *numberCompares,

int *numberMoves);

void DoInsertionSort(int *A,const int n,

bool (*ShouldInsert)(const int LHS,const int RHS),

int *numberCompares,

int *numberMoves);

bool Ascending(const int LHS,const int RHS);

bool Descending(const int LHS,const int RHS);

int n;

SetRandomSeed();

printf("n? ");

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

{

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

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

int numberCompares;

int numberMoves;

BuildRandomArray(A,n);

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

printf("# of ascending-order inversions is %d ",

NumberOfInversions(A,n,Ascending));

printf("# of descending-order inversions is %d ",

NumberOfInversions(A,n,Descending));

CopyArray(copyA,A,n);

DoBubbleSort(copyA,n,Ascending,&numberCompares,&numberMoves);

DisplayArraySlice("Bubble Sort (Ascending)",copyA,n,0,n-1);

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

printf("# of moves is %d ",numberMoves);

printf("# of ascending-order inversions is %d ",

NumberOfInversions(copyA,n,Ascending));

CopyArray(copyA,A,n);

DoBubbleSort(copyA,n,Descending,&numberCompares,&numberMoves);

DisplayArraySlice("Bubble Sort (Descending)",copyA,n,0,n-1);

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

printf("# of moves is %d ",numberMoves);

printf("# of descending-order inversions is %d ",

NumberOfInversions(copyA,n,Descending));

CopyArray(copyA,A,n);

DoSelectionSort(copyA,n,Ascending,&numberCompares,&numberMoves);

DisplayArraySlice("Selection Sort (Ascending)",copyA,n,0,n-1);

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

printf("# of moves is %d ",numberMoves);

printf("# of ascending-order inversions is %d ",

NumberOfInversions(copyA,n,Ascending));

CopyArray(copyA,A,n);

DoSelectionSort(copyA,n,Descending,&numberCompares,&numberMoves);

DisplayArraySlice("Selection Sort (Descending)",copyA,n,0,n-1);

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

printf("# of moves is %d ",numberMoves);

printf("# of descending-order inversions is %d ",

NumberOfInversions(copyA,n,Descending));

CopyArray(copyA,A,n);

DoInsertionSort(copyA,n,Ascending,&numberCompares,&numberMoves);

DisplayArraySlice("Insertion Sort (Ascending)",copyA,n,0,n-1);

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

printf("# of moves is %d ",numberMoves);

printf("# of ascending-order inversions is %d ",

NumberOfInversions(copyA,n,Ascending));

CopyArray(copyA,A,n);

DoInsertionSort(copyA,n,Descending,&numberCompares,&numberMoves);

DisplayArraySlice("Insertion Sort (Descending)",copyA,n,0,n-1);

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

printf("# of moves is %d ",numberMoves);

printf("# of descending-order inversions is %d ",

NumberOfInversions(copyA,n,Descending));

free(A);

free(copyA);

printf(" n? ");

}

system("PAUSE");

return( 0 );

}

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

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

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

{

int i;

for (i = 0; i

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

}

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

void CopyArray(int copyA[],const int A[],const int n)

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

{

int i;

// for (i = 0; i

i = 0;

TOL1:

if ( !(i

{

copyA[i] = A[i];

i++;

goto TOL1;

}

BOL1:

; // Do nothing

}

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

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

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

{

Student provides missing code to display A[i], i [ L,R ], 10 elements per line.

See the Sample Program Dialog for detailed formatting requirements. You are allowed to

use "real" loop control cJnstructs.

}

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

int NumberOfInversions(const int A[],const int n,bool (*AreInverted)(const int LHS,const int RHS))

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

{

int i,j,r;

for (i = 0,r = 0; i

for (j = i+1; j

if ( AreInverted(A[i],A[j]) ) r++;

return( r );

}

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

bool Ascending(const int LHS,const int RHS)

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

{

return( (LHS > RHS) ? true : false );

}

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

bool Descending(const int LHS,const int RHS)

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

{

return( LHS

}

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

void DoBubbleSort(int A[],const int n,

bool (*ShouldSwap)(const int LHS,const int RHS),

int *numberCompares,

int *numberMoves)

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

{

Student provides missing code to Bubble Sort the n elements in the array A

(A[i], i [ 0,n-1 ]) using the function-pointer parameter ShouldSwap()

to determine whether adjacent elements should be swapped. Count the

number of comparisons, *numberCompares, and the number of moves, *numberMoves,

needed to sort the n elements. The non-goto version of the Bubble Sort

(taken from page 101 of our text book)is given below.

int i,pass;

bool swapMade;

pass = 1;

*numberCompares = 0;

*numberMoves = 0;

do

{

swapMade = false;

for (i = 0; i

{

*numberCompares += 1;

if ( ShouldSwap(A[i],A[i+1]) )

{

int T = A[i]; A[i] = A[i+1]; A[i+1] = T;

*numberMoves += 3;

swapMade = true;

}

}

pass++;

} while ( swapMade );

}

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

void DoSelectionSort(int *A,const int n,

bool (*ShouldSelect)(const int LHS,const int RHS),

int *numberCompares,

int *numberMoves)

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

{

Student provides missing code to Selection Sort the n elements in the array A

(A[i], i [ 0,n-1 ]) using the function-pointer parameter ShouldSelect()

to determine whether an element should be selected. Count the

number of comparisons, *numberCompares, and the number of swaps, *numberMoves,

needed to sort the n elements. The non-goto version of the Selection Sort

(taken from page 99 of our text book) is given below.

int i;

*numberCompares = 0;

*numberMoves = 0;

for (i = 0; i

{

int T,j,select = i;

for (j = i+1; j

{

if ( (*ShouldSelect)(A[select],A[j]) ) select = j;

*numberCompares += 1;

}

T = A[i]; A[i] = A[select]; A[select] = T;

++*numberMoves, *numberMoves += 1, (*numberMoves)++;

}

}

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

void DoInsertionSort(int A[1],const int n,

bool (*ShouldInsert)(const int LHS,const int RHS),

int *numberCompares,

int *numberMoves)

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

{

Student provides missing code to Insertion Sort the n elements in the array A

(A[i], i [ 0,n-1 ]) using the function-pointer parameter ShouldInsert()

to determine when/where an element should be inserted. Count the

number of comparisons, *numberCompares, and the number of moves, *numberMoves,

needed to sort the n elements. The non-goto version of the Insertion Sort

(taken from page 134 of our text book) is given below.

int i;

*numberCompares = 0;

*numberMoves = 0;

for (i = 1; i

{

int v = A[i];

int j = i-1;

*numberMoves += 1;

while ( (j >= 0) && (*ShouldInsert)(A[j],v) )

{

*numberCompares += 1;

A[j+1] = A[j];

*numberMoves += 1;

j--;

}

A[j+1] = v;

*numberMoves += 1;

}

}

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

// 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))] );

}

Problemm Allow the user to input n, the number of integer elements stored in a dynamically-allocated array en 1. randomly choose the contents of A] from the interval [ 1,10*n ]; 2. use the void-returning function DisplayArraySlice) to display the unsorted contents of A[]; 3. display the number of inversions of the elements of A[]; 4. make a copy-of-A[]; use the void-returning function DoBubbleSort0 (prototyped below) to sort the copy-of- A[] into ascending order; display the sorted contents of copy-of-A[]; display the statistics-number of compares, the number of moves, and the number of inversions; 5. make a copy-of-A[]; use the void-returning function DoBubbleSort0 again to sort the copy-of- A [] but this time into descending order; display the sorted contents of copy-of-A [1; display the statistics-number of compares, the number of moves, and the number of inversions; 6. repeat (4) and (5) using DoSelectionSort0 (prototyped below); and, 7. repeat (4) and (5) using DoInsertionSort) (prototyped below) The 3 sorting functions are instrumented to count both the number-of-key-comparisons and the number- of-element-moves required during the execution of sort. You must use goto-statements to express the iterations (to re-implement the loops) found in the functions DoBubbleSort) and DoSelectionSort) and DoInsertionSort)! Problemm Allow the user to input n, the number of integer elements stored in a dynamically-allocated array en 1. randomly choose the contents of A] from the interval [ 1,10*n ]; 2. use the void-returning function DisplayArraySlice) to display the unsorted contents of A[]; 3. display the number of inversions of the elements of A[]; 4. make a copy-of-A[]; use the void-returning function DoBubbleSort0 (prototyped below) to sort the copy-of- A[] into ascending order; display the sorted contents of copy-of-A[]; display the statistics-number of compares, the number of moves, and the number of inversions; 5. make a copy-of-A[]; use the void-returning function DoBubbleSort0 again to sort the copy-of- A [] but this time into descending order; display the sorted contents of copy-of-A [1; display the statistics-number of compares, the number of moves, and the number of inversions; 6. repeat (4) and (5) using DoSelectionSort0 (prototyped below); and, 7. repeat (4) and (5) using DoInsertionSort) (prototyped below) The 3 sorting functions are instrumented to count both the number-of-key-comparisons and the number- of-element-moves required during the execution of sort. You must use goto-statements to express the iterations (to re-implement the loops) found in the functions DoBubbleSort) and DoSelectionSort) and DoInsertionSort)