C Programming Questions On Non Recursive Sorting Techniques

Try To Answer These?

a) What modification is required to insertion sort to sort the integers in descending order?



Answer:We just have check whether the integer before key is less than key or not. If it is, we have to swap it.

Modified Code:

void InsertionSort(int arr[], int n)
{

	int Key,i,j;

	for(i=1;i<n;i++)
	{

	Key=arr[i];

	j=i-1;


	while( j>=0 && arr[j]<Key) Here We have replaces > with <
	{
		arr[j+1]=arr[j];
		j=j-1;
	}

	arr[j+1]=Key;

	}
}

Respective Program: C program For Insertion Sort

b)What modifications are required to bubble sort to sort the integers in descending order?



Answer:We have to check whether previous integer is less than the next one and if it is then we have to swap it.

Modified Code:

	for(i=1;i<n;i++)
	{
		for(j=0;j<n-i;j++)
		{	if(a[j+1]>a[j]) // Observe the change here in comparison operator
			{
			temp=a[j];
			a[j]=a[j+1];
			a[j+1]=temp; 
			}
		}
	}

Respective Program:C Program To Sort Array Elements In Descending Order Using Bubble Sort

c) What modifications are required to bubble sort to count the number of swaps?



Answer: Introduce a counter variable swap in if like given below:
	for(i=1;i<n;i++)
	{
		for(j=0;j<n-i;j++)
		{	if(a[j+1]>a[j])
			{
			temp=a[j];
			a[j]=a[j+1];
			a[j+1]=temp;
			swap++; // Observe Here
			}
		}
	}

d) What modifications are required to insertion sort to count the number of key comparisons?



Answer: Introduce a counter variable 'count' to count number of key comparisons.
void InsertionSort(int arr[], int n)
{

	int Key,i,j,count=0;

	for(i=1;i<n;i++)
	{

	Key=arr[i];

	j=i-1;

	count++; // Observe Here
	while( j>=0 && arr[j]<Key)
	{
		arr[j+1]=arr[j];
	j=j-1;
	}

	arr[j+1]=Key;

	}
}

e) What modifications are required to improve bubble sort to stop further passes if the file is already sorted that is when there are no more swaps?



Answer: Introduce a flag variable and check the flag at end of first pass. Depending on to value of flag decide whether to proceed or not.
	for(i=1;i<size;i++)
	{
	flag=0;
		for(j=0;j<size-i;j++)
		{
			if(arr[j]<arr[j+1])
			{
			temp=arr[j];
			arr[j]=arr[j+1];
			arr[j+1]=temp;
			flag=1;
			} 
		}

	if(flag==0)
	break;
	} 

f) Compare the system time taken by insertion sort and bubble sort by using 'time' command on a random file of size 10000 or more.
$ time ./a.out



Answer: With the help of code given below calculate time taken by bubble sort and insertion sort to sort the files and then compare them.

     #include <time.h>
     
     clock_t start, end; // Declaring two variables start and end of type clock_t
     double cpu_time_used;
     
     start = clock(); // Initializing start with current system time

     /* Put Put the code here that you want to calculate time for */

     end = clock(); Getting final system time after execution of all work

     cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; // Calculating the time taken i.e end time - start time

g) What modifications are required to output the array contents after every pass of the sorting algorithm?



	for(i=1;i<size;i++)
	{

			/* Sorting Code Here */

// Display the array in each pass after all statements are executed for a pass.

		for(k=0;k<n;k++)
			printf(" %d ",arr[k]);

	}