# C Programming Questions On Non Recursive Sorting Techniques

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;

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

}
```