## Answers

//header file

#ifndef INSERTIONSORT_H

#define INSERTIONSORT_H

int insertionSort(int arr[],int size,int *ncompares_ptr,int *nswaps_ptr);

#endif

//c file

#include <stdio.h>

#include <math.h>

#include "insertionsort.h"//including header

// A utility function to print an array of size n

void printArray(int arr[], int n)

{

int i;

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

printf("%d ", arr[i]);

printf("\n");

}

/* Function to sort an array using insertion sort*/

int insertionSort(int arr[],int size,int *ncompares_ptr,int *nswaps_ptr)

{

int i, key, j;

int n=size;

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

{

key = arr[i];

j = i-1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > key)

{

//incrementing number of comparisions and swaps

(*ncompares_ptr)++;

(*nswaps_ptr)++;

arr[j+1] = arr[j];

j = j-1;

}

arr[j+1] = key;

//printArray(arr, n);

}

//returning sum of comparision and swaps

return (*nswaps_ptr)+(*ncompares_ptr);

}

/* Driver program to test insertion sort */

int main()

{

int arr[] = {21,14,32,10,44,8,2,11,20,26};

int n = sizeof(arr)/sizeof(arr[0]);

printf("Array before sorting:\n");

printArray(arr, n);

int c=0,s=0;;

int sum = insertionSort(arr, n,&c,&s);

printf("Array after sorting:\n");

printArray(arr, n);

printf("Comparisions : %d\n Swaps : %d\n Sum : %d\n",c,s,sum);

return 0;

}

output:

Array before sorting:

21 14 32 10 44 8 2 11 20 26

Array after sorting:

2 8 10 11 14 20 21 26 32 44

Comparisions : 24

Swaps : 24

Sum : 48

Process exited normally.

Press any key to continue . . .