//C program to implement Merge Sort//
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#define MAXARRAY 10
void mergesort(int a[], int low, int high);
void main(void)
{
int array[MAXARRAY];
int i = 0;
clrscr();
randomize();
/* load some random values into the array */
for(i = 0; i < MAXARRAY; i++)
{
array[i] = rand() % 100;
}
/* array before mergesort */
printf("Before :");
for(i = 0; i < MAXARRAY; i++)
{
printf(" %d", array[i]);
}
printf("\n");
mergesort(array, 0, MAXARRAY - 1);
/* array after mergesort */
printf("Mergesort :");
for(i = 0; i < MAXARRAY; i++)
{
printf(" %d", array[i]);
}
printf("\n");
getch();
}
void mergesort(int a[], int low, int high)
{
int i = 0;
int length = high - low + 1;
int pivot = 0;
int merge1 = 0;
int merge2 = 0;
int *working;
working=(int*)malloc(length*2);
if(low == high)
{
return;
}
pivot = (low + high) / 2;
mergesort(a, low, pivot);
mergesort(a, pivot + 1, high);
for(i = 0; i < length; i++)
{
working[i] = a[low + i];
}
merge1 = 0;
merge2 = pivot - low + 1;
for(i = 0; i < length; i++) {
{
if(merge2 <= high - low)
if(merge1 <= pivot - low)
if(working[merge1] > working[merge2])
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
else
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#define MAXARRAY 10
void mergesort(int a[], int low, int high);
void main(void)
{
int array[MAXARRAY];
int i = 0;
clrscr();
randomize();
/* load some random values into the array */
for(i = 0; i < MAXARRAY; i++)
{
array[i] = rand() % 100;
}
/* array before mergesort */
printf("Before :");
for(i = 0; i < MAXARRAY; i++)
{
printf(" %d", array[i]);
}
printf("\n");
mergesort(array, 0, MAXARRAY - 1);
/* array after mergesort */
printf("Mergesort :");
for(i = 0; i < MAXARRAY; i++)
{
printf(" %d", array[i]);
}
printf("\n");
getch();
}
void mergesort(int a[], int low, int high)
{
int i = 0;
int length = high - low + 1;
int pivot = 0;
int merge1 = 0;
int merge2 = 0;
int *working;
working=(int*)malloc(length*2);
if(low == high)
{
return;
}
pivot = (low + high) / 2;
mergesort(a, low, pivot);
mergesort(a, pivot + 1, high);
for(i = 0; i < length; i++)
{
working[i] = a[low + i];
}
merge1 = 0;
merge2 = pivot - low + 1;
for(i = 0; i < length; i++) {
{
if(merge2 <= high - low)
if(merge1 <= pivot - low)
if(working[merge1] > working[merge2])
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
else
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
}
}
}
No comments:
Post a Comment