// Program by Akash Tripathi (@proakash256)
// To Sort an Array using Merge Sort Technique
// Merge Sort is a Divide and Conquer Algorithm.
// It divides the Input Array into two halves ,
// calls itself for the two halves ,
// and then merges the two halves in such a way
// that they are Sorted.
// mergeSort() function (Recursive) is used to
// break the Array into smaller parts.
// merge() funcion is used to merge those smaller parts
// and hence Sorting them.
// Algorithm :
// 1. Find the middle pont to divide the array
// middle = (low + high) / 2;
// 2. Call mergeSort() for the first half
// mergeSort(ar , low , middle)
// 3. Call mergeSort() for the second half
// mergeSort(ar , (middle + 1) , high)
// 4. Merge the two halves
// merge(ar , low , middle , high)
// Time Complexity - O(n logn) (Always)
// Space Complexity - O(n)
#include <stdio.h>
void merge(int ar[], int low, int mid, int high, char c)
{
int i, j, k;
int B[(high - low + 1)];
i = low;
j = mid + 1;
k = low;
if (c == '1')
{
while (i <= mid && j <= high)
{
if (ar[i] < ar[j])
{
B[k] = ar[i];
i = i + 1;
k = k + 1;
}
else
{
B[k] = ar[j];
j = j + 1;
k = k + 1;
}
}
}
else if (c == '2')
{
while (i <= mid && j <= high)
{
if (ar[i] > ar[j])
{
B[k] = ar[i];
i = i + 1;
k = k + 1;
}
else
{
B[k] = ar[j];
j = j + 1;
k = k + 1;
}
}
}
while(i <= mid)
{
B[k] = ar[i];
k = k + 1;
i = i + 1;
}
while(j <= high)
{
B[k] = ar[j];
k = k + 1;
j = j + 1;
}
for(i = low; i <= high; i = i + 1)
ar[i] = B[i];
}
void mergeSort(int ar[], int low, int high, char c)
{
int mid;
if (low < high)
{
mid = (low + high) / 2;
mergeSort(ar, low, mid, c);
mergeSort(ar, (mid + 1), high, c);
merge(ar, low, mid, high, c);
}
}
int main()
{
int n;
printf("Enter the number of elements
you want to enter in the array : ");
scanf("%d", &n);
int ar[n];
printf("\nEnter the elements :\n");
for (int i = 0; i < n; i = i + 1)
scanf("%d", &ar[i]);
int low = 0, high = n - 1;
printf("\nEnter 1 to Sort in Ascending Order\n");
printf("Enter 2 to Sort in Descending Order\n");
printf("Enter your Choice : ");
char c;
scanf(" %c", &c);
if (c == '1')
{
mergeSort(ar, low, high, c);
}
else if (c == '2')
{
mergeSort(ar, low, high, c);
}
else
printf("Sorry Wrong Choice...\n");
printf("\nThe Sorted array is :\n");
for (int i = 0; i < n; i = i + 1)
printf("%d\n", ar[i]);
return 0;
}
Comments
Post a Comment