New Topic/Question
Reply
I have a question regarding sorting algorithms. Well as I know, the insertion sort is faster than the merge sort. And I have implemented this and measured their running time for different inputs and found out that it's true the insertion sort is faster than the merge sort. Now, here's my question, is there a way in which we can modify the code of the merge sort to become as fast as insertion sort? I mean what would happen if we call for example the insertion sort as a subroutine within the merge sort code? I've been asking myself this question and thought i'd try implementing it myself, but i keep getting an error.
Anyway, here's the code:
#include <ctime>
#include <iostream>
using namespace std;
void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);
int main()
{
clock_t start = clock();
int arrayOne[10];
int arrayTwo[10];
int A[10];
mergeSort(arrayOne, arrayTwo, 10);
for (int i = 0; i < 10; i++)
{
cout << arrayOne[i] << " ";
}
insertion_sort(A,10);
for(int x=0;x<10;x++)
{
cout << "The modified merge sort" << endl;
cout << A[x] << endl;
}
clock_t ends = clock();
cout << "Running Time : " << (double) (ends - start) / CLOCKS_PER_SEC << endl;
return 0;
}
void insertion_sort(int x[],int length)
{
int key,i;
for(int j=1;j<length;j++)
{
key=x[j];
i=j-1;
while(x[i]>key && i>=0)
{
x[i+1]=x[i];
i--;
}
x[i+1]=key;
}
}
void mergeSort(int numbers[], int temp[], int array_size)
{
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 += 1;
left += 1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos += 1;
mid += 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left += 1;
tmp_pos += 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid += 1;
tmp_pos += 1;
}
for (i=0; i < num_elements; i++)
{
numbers[right] = temp[right];
right -= 1;
}
}
The error I keep getting is: insertion_sort is not identified. how's that possible? I did identify it.
Is there something wrong with the code? or is the idea itself not do-able?
Thanx in advance!
MultiQuote
| 