Question

1. Consider the following well-known sorting algorithm, which is studied later
in the book, with a counter inserted to count the number of key comparisons.
ALGORITHM SortAnalysis(A[0..n − 1])
//Input: An array A[0..n − 1] of n orderable elements
//Output: The total number of key comparisons made
count ←0
for i ←1 to n − 1 do

v ←A[i]
j ←i − 1
while j ≥ 0 and A[j ]> v do
count ←count + 1
A[j + 1]←A[j ]
j ←j − 1
A[j + 1]←v
return count
Is the comparison counter inserted in the right place? If you believe it is, prove
it; if you believe it is not, make an appropriate correction.

Run the program of Problem 1, with a properly inserted counter (or counters) for the number of key comparisons, on 20 random arrays of sizes 1000, 2000, 3000, . . . , 20,000. b. Analyze the data obtained to form a hypothesis about the algorithm’s average-case efficiency. c. Estimate the number of key comparisons we should expect for a randomly generated array of size 25,000 sorted by the same algorithm.

please provide the solution step by step

Answer 1

//count is at wrong place it is out of the loop therefore it never count the no. of comparision

//below is the complete code that run and compute the total no. of comparision made to sort the randomly generated array

//"get_data function" is used to assign random value to the arrays like a[1000],b[2000],c[25000]

//"sort function" is used to sort the array

//sort function takes two argument one is which is to be sort another is the size of the array

//function work in such a way that it set the smallest no first

//step 1:- again=0

//step 2:- for loop iterate element by element,

//step 3:- if array is not sorted at that value of i then if "a[i+1]<a[i] =True",then a[i+1] swap with a[i], again=1

// if "a[i+1]<a[i] =false" that means upto that value of i array is sorted and program move to next step

//step 4:- count=count+1 and i=i+1.... and continue step2 to step 4 till i<iter(or size-1)

//step 5:- while loop check the value of again. if again=1 that means array is not sorted and loop run again and step1 to step5

// whereas if again=0 that means array is sorted and while loop terminated.

//step 6:- count is return to the main

#include <stdio.h>

#include <stdlib.h>

int sort(int array[], size_t size)

{

int i = 0;

int temp,count=0;

int again = 1;

int iteration = size - 1;

do {

again = 0;

for(i=0; i < iteration; ++i)

{

if (array[i + 1] < array[i]) //if array is not sorted this condition is true that makes again=1 while rerun the do-while

{ //followed by for loop otherwise again is set to 0 before terminates the loop

temp = array[i]; //swapping

array[i] = array[i + 1];

array[i + 1] = temp;

again = 1;

}

count++;

}

--iteration;

} while (again);

return count;

}

//function used to print array

void print_data(int array[],size_t size)

{

unsigned i = 0;

for(; i < size; ++i)

{

printf("%d\n", array[i]);

}

}

//get_data method is used to assign random value to the arrays like a[1000],b[2000],c[25000]

void get_data(int array[],size_t size)

{

unsigned i = 0;

for(; i < size; ++i)

{

array[i] = rand() %100;

}

}

int main(void)

{

int a[1000], b[2000], c[25000];

get_data(a, sizeof a / sizeof (int));

get_data(b, sizeof b / sizeof (int));

get_data(c, sizeof c / sizeof (int));

int count = sort(a, sizeof a / sizeof (int));

printf("%d\n",count);

//print_data(a, sizeof a / sizeof (int));

count = sort(b, sizeof b / sizeof (int));

printf("%d\n",count);

count = sort(c, sizeof c / sizeof (int));

printf("%d\n",count);

//print_data(c,sizeof c / sizeof (int));

exit(0);

}

//estimated count for 25000 size array is 312453570.