1. Consider the following well-known sorting algorithm, which is studied later i
ID: 3591869 • Letter: 1
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
Explanation / Answer
//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 ", 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 ",count);
//print_data(a, sizeof a / sizeof (int));
count = sort(b, sizeof b / sizeof (int));
printf("%d ",count);
count = sort(c, sizeof c / sizeof (int));
printf("%d ",count);
//print_data(c,sizeof c / sizeof (int));
exit(0);
}
//estimated count for 25000 size array is 312453570.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.