Data Structures Practical 10
Question 1
Modify the Insertion Sort algorithm to use binary search for finding the correct position to insert the current element.
bininsertion.c
C
#include <stdio.h>
#include <conio.h>
int binarySearch(int arr[], int item, int low, int high)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (item == arr[mid])
{
return mid + 1;
}
if (item > arr[mid])
{
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
void binaryInsertionSort(int arr[], int n)
{
int i, j, selected, insertPos;
for (i = 1; i < n; i++)
{
selected = arr[i];
insertPos = binarySearch(arr, selected, 0, i - 1);
for (j = i - 1; j >= insertPos; j--)
{
arr[j + 1] = arr[j];
}
arr[insertPos] = selected;
}
}
void main()
{
int arr[100], n, i;
clrscr();
printf("Enter number of elements (1-100): ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
binaryInsertionSort(arr, n);
printf("\nSorted array in ascending order:\n");
for (i = 0; i < n; i++)
{
printf("%d\t", arr[i]);
}
getch();
}
Output
Question 2
Use the Insertion Sort algorithm to count the number of inversions in an array. An inversion is a pair of elements where the earlier element is greater than the later element.
inversioncount.c
C
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define max 50
int insertion(int arr[], int size);
void main()
{
int arr[max];
int i, size;
int total_inversions = 0;
clrscr();
printf("Enter the number of elements in the array :");
scanf("%d", &size);
printf("Enter array elements :");
for (i = 0; i < size; i++)
{
printf("\nEnter element %d: ", i + 1);
scanf("%d", &arr[i]);
}
total_inversions = insertion(arr, size);
printf("\nTotal number of inversions: %d\n", total_inversions);
printf("\nThe sorted elements are :\n");
for (i = 0; i < size; i++)
printf("%d\t", arr[i]);
getch();
}
int insertion(int array[], int size)
{
int i, j, temp;
int inv_count = 0;
for (i = 1; i < size; i++)
{
temp = array[i];
for (j = i - 1; j >= 0; j--)
{
if (temp < array[j])
{
array[j + 1] = array[j];
inv_count++;
}
else
{
break;
}
}
array[j + 1] = temp;
}
return inv_count;
}
Output
