Merge sort
This one is also based on divide and conquer strategy just like quick sort.Dividing the array into two subarrays of size n/2. Then recursively solve two subarrays and then combine them using merge.Keep dividing the array recursively in 2 parts till left with subarray of one element.Then call merge to combine two subarrays.Starting with combining two subarrays of size 1, merge compares two to put them in sorted sequence.
Try the following snippet:
#include<stdio.h>
#define MAX_SIZE 10
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);
void main()
{
int arr[MAX_SIZE];
int temp[MAX_SIZE];
int i,pos;
for(i=0;i<MAX_SIZE;i++)
{
printf("\n enter the element : : %d ",i+1);
scanf("%d",&arr[i]);
}
m_sort(arr, temp, 0, MAX_SIZE - 1);
for(i=0;i<MAX_SIZE;i++)
{
printf("\n element %d",arr[i]);
}
getchar();
getchar();
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
This one is also based on divide and conquer strategy just like quick sort.Dividing the array into two subarrays of size n/2. Then recursively solve two subarrays and then combine them using merge.Keep dividing the array recursively in 2 parts till left with subarray of one element.Then call merge to combine two subarrays.Starting with combining two subarrays of size 1, merge compares two to put them in sorted sequence.
Try the following snippet:
#include<stdio.h>
#define MAX_SIZE 10
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);
void main()
{
int arr[MAX_SIZE];
int temp[MAX_SIZE];
int i,pos;
for(i=0;i<MAX_SIZE;i++)
{
printf("\n enter the element : : %d ",i+1);
scanf("%d",&arr[i]);
}
m_sort(arr, temp, 0, MAX_SIZE - 1);
for(i=0;i<MAX_SIZE;i++)
{
printf("\n element %d",arr[i]);
}
getchar();
getchar();
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
No comments:
Post a Comment