-
Merge Sort
Please, how to make a merge sort program -in c++-which the user enters the numbers he wants to be sorted & then the program display the numbers after sorting.
Or
how to make modifications on the following program to do what iwant -enter numbers & then dispaly the sorted numbers.
Code:
void mergeSort(int numbers[], int temp[], int array_size=6)//
{
m_sort(numbers, temp, 0, array_size - 1);
}
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;
}
}
-
Show us what you have tried and we will help you.
To me this sounds an aweful lot like homework.
-
It was homework but
May be it was homework but the problem for me was misunderstanding the recursion
but now i undestand it .
I have made little modification on program in order to make what iwant-it's completed.
Code:
#include<iostream.h>
#include <stdlib.h>
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 i;
int *numbers;
int *temp;
int len;
cout<<"How many numbers do you want to sort??"<<endl;
cin>>len;
numbers=new int[len];
temp=new int[len];
for (i = 0; i < len; i++)
{
cout<<"Enter number"<<i+1<<endl;
cin>>numbers[i];
}
//perform merge sort on array
m_sort(numbers, temp, 0, len - 1);
cout<<"Done with sort"<<endl;
for (i = 0; i < len; i++)
cout<<numbers[i]<<endl;
}
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;
}
}