Algorithm Development:

Merge Sort is one of the best examples of Divide & Conquer algorithm.

Divide & Conquer algorithm has 3 steps:

1. Divide: Breaking the problem into sub problems.

2. Conquer: Recursively solving the sub problems.
3. Combine: Combining the solutions to get the final result.

In Merge sort, we divide the array recursively in two halves, until each sub-
array contains a single element, and then we merge the sub-array in a way that it
results into a sorted array. merge() function merges two sorted sub-arrays into
one, wherein it assumes that array[l .. n] and arr[n+1 .. r] are sorted.
Merge Sort Algorithm
MergeSort(arr[], l, r), where l is the index of the first element & r is the index of
the last element.
If l<r
1. Find the middle index of the array to divide it in two halves:
m = (l+r)/2
2. Call MergeSort for first half:
mergeSort(array, l, m)
3. Call mergeSort for second half:
mergeSort(array, m+1, r)
4. Recursively, merge the two halves in a sorted manner, so that only one sorted
array is left:
merge(array, l, m, r)
To sort an array using Merge sort, following is the process
We take two variables l & r where l stores the staring index & stores the last
index of the array.
Next, we find the mid of the array to break it in two halves.
Formula to do so is (l+r)/2 and mark the middle element as m.
Next step is to break the given array into two subarrays from the middle
element, i.e. from index p to m & m+1 to r.
We continue to break the subarrays until we reach to a level where each sub
array contains 1 element.
Next we merge the sub-array recursively in a sorted order, so that we finally get
a sorted array.

C Program to implement merge sort:

#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
// Merge Function
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
void main()
{
int arr[] = {85, 24, 63, 45, 17, 31, 96, 50};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Implementing merge sort\n");
printf("Given array is:");
printf("\n");
printArray(arr,arr_size);
printf("Sorted array is");
mergeSort(arr,0,arr_size - 1);
printf("\n");
printArray(arr,arr_size);
getch();
}

Output:
Similarly repeat the process for successive iterations until end of array is
reached, sorting the elements one by one as shown below:
C program to sort the elements of an array by selection sort method:
#include <stdio.h>
#include<conio.h>
void main()
{
int n=10;
int i, j, position, temp;
int arr[10]={6,12,0,18,11,99,55,45,34,2};
printf("Array Contents are : \n");
for (i = 0; i<=(n-1); i++)
{
printf("%d\t",arr[i]);
}

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

{
position = i;
for (j = i + 1; j < n; j++)
{
if (arr[position] > arr[j])
position = j;
}
if (position != i)
{
temp = arr[i];
arr[i] = arr[position];
arr[position] = temp;
}
}
printf("\n");
printf("Sorted Array with selection method is as follows:\n");
 for (i = 0;i<=(n-1);i++)
printf("%d\t", arr[i]);
getch();
}

Output:
C program to implement sort by exchange/bubble sort
#include<stdio.h>
#include<conio.h>
void print(int a[], int n) //function to print array elements
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ",a[i]);
}
}
void bubble(int a[], int n) // function to implement bubble sort
{
int i, j, temp;
for(i = 0; i < n; i++)
{
for(j = i+1; j < n; j++)
{
if(a[j] < a[i])
 {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
void main ()
{
int i, j,temp;
int a[5] = { 10, 35, 32, 13, 26};
int n = sizeof(a)/sizeof(a[0]);
printf("Implementing bubble sort\n");
printf("Before sorting array elements are - \n");
print(a, n);
bubble(a, n);
printf("\nAfter sorting array elements are - \n");
print(a, n);
getch();
}

Output:
Following are the array contents after each iteration applying selection sort
method:
C Program to implement insertion sort:
#include <stdio.h>
#include<conio.h>
void insert(int a[], int n) /* function to sort an array with insertion sort */
{
int i, j, temp;
for (i = 1; i < n; i++)
{
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than temp
to one position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
 }
void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
void main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Implementing insertion sort\n");
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
getch();
}
Output:
To implement this idea, a method
 Write a C Program to implement sort by diminishing increment or shell
sort
#include <stdio.h>
#include<conio.h>
/* function to implement shellSort */
void shell(int a[], int n)
{
/* Rearrange the array elements at n/2, n/4, ..., 1 intervals */
 for (int interval = n/2; interval > 0; interval /= 2)
{
for (int i = interval; i < n; i += 1)
{
/* store a[i] to the variable temp and make the ith position empty */
int temp = a[i];
int j;
for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
a[j] = a[j - interval];

// put temp (the original a[i]) in its correct position

a[j] = temp;
}
}

}
void printArr(int a[], int n) /* function to print the array elements */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
void main()
{
int a[] = { 33, 31, 40, 8, 12, 17, 25, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
 printArr(a, n);
shell(a, n);
printf("\nAfter applying shell sort, the array elements are - \n");
printArr(a, n);
getch();
}

Output:

Consider the following set of numbers to be sorted

Applying the mechanism of shell sort to the above unsorted array, we have the
below array after the first pass.
That is :
C Program to implement quick sort or partition sort by the Hoare’s
method
#include<stdio.h>
#include<conio.h>
void quicksort(int number[25],int first,int last)
{
int i, j, pivot, temp;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j)
{
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
void main()
{
int i, count, number[25];
printf("Enter total of elements to be sorted (Max. - 25): ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<=(count-1);i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("The Sorted Order as per quick sort is:\n");
for(i=0;i<=(count-1);i++)
printf(" %d\t",number[i]);
getch();
}

Output:

In order to implement this on any given data set, we have to first sort the data
set in increasing order. Once this is done,
C Program to implement binary search for a given set of sorted numbers.
Output:
#include <stdio.h>
#include<conio.h>
void main()
{
int i, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter element %d in ascending order\n",i+1);
scanf("%d",&array[i]);
}
printf("Entered elements are\n");
for (i = 0; i < n; i++)
{
printf("%d\t",array[i]);
}
printf("\n");
printf("Enter value to find\n");
scanf("%d",&search);

first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last)
{
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
{
printf("%d found at location %d.\n", search, middle+1);
 break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if(first > last)
printf("Not found! %d isn't present in the list.\n", search);
getch();
}
Output:
To implement this technique of fast search,we apply the technique of
normalizing the data. Normalising technique involves applying transformation
for each element in the list before we search it.
C Program to implement Hash Search algorithm
#include<stdio.h>
#include<limits.h>
void insert(int ary[],int hFn, int size)
{
int element,pos,n=0;
printf("Enter key element to insert\n");
scanf("%d",&element);
pos = element%hFn;
while(ary[pos]!= INT_MIN)
{ // INT_MIN and INT_MAX indicates that cell is empty. So if cell is empty
loop will break and goto bottom of the loop to insert element
if(ary[pos]== INT_MAX)
break;
pos = (pos+1)%hFn;
n++;
if(n==size)
break; // If table is full we should break, if we dont check this, loop will go to
infinite loop.
}
if(n==size)
printf("Hash table was full of elements\nNo Place to insert this element\n\n");
else
ary[pos] = element; //Inserting element
}
void delete(int ary[],int hFn,int size)
{
int element,n=0,pos;
printf("Enter element to delete\n");
scanf("%d",&element);
pos = element%hFn;
while(n++ != size)
{
if(ary[pos]==INT_MIN)
{
printf("Element not found in hash table\n");
break;
}
else if(ary[pos]==element)
{
ary[pos]=INT_MAX;
printf("Element deleted\n\n");
break;
}
else
{
pos = (pos+1) % hFn;
}
}
if(--n==size)
printf("Element not found in hash table\n");
}
void search(int ary[],int hFn,int size)
{
int element,pos,n=0;
printf("Enter element you want to search\n");
scanf("%d",&element);
pos = element%hFn;
while(n++ != size)
{
if(ary[pos]==element)
{
printf("Element found at index %d\n",pos);
break;
}
else if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN)
pos = (pos+1) %hFn;
}
if(--n==size)
printf("Element not found in hash table\n");
}
void display(int ary[],int size)
{
int i;
printf("Index\tValue\n");
for(i=0;i<size;i++)
printf("%d\t%d\n",i,ary[i]);
}
void main()
{
int size,hFn,i,choice;
printf("Enter size of hash table\n");
scanf("%d",&size);
int ary[size];
printf("Enter hash function [if mod 10 enter 10]\n");
scanf("%d",&hFn);
for(i=0;i<size;i++)
ary[i]=INT_MIN; //Assigning INT_MIN indicates that cell is empty
do
{
printf(" 1-> Insert\n 2-> Delete\n 3-> Display\n 4-> Searching\n 0-> Exit\n");
printf("Enter your choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert(ary,hFn,size);
break;
case 2:
delete(ary,hFn,size);
break;
case 3:
display(ary,size);
break;
case 4:
search(ary,hFn,size);
break;
default:
printf("Enter correct choice\n");
break;
}
}while(choice);
getch();
}
Output: