-
help with merge sort
Write a function to recursively and visually do a merge-sort of a
given array of 20 numbers. Be sure that after each merge the entire contents of the array
are printed to the screen, including the number of merges so far that the
current array arrangement represents.
An example run for 5 numbers would look like:
Enter 5 integers: 5 0 1 4 3
The interim results of the merge_sort algorithm are:
INDEX: 0 1 2 3 4
--------------------
Merge # 1: 5 0 1 4 3
Merge # 2: 0 5 1 4 3
Merge # 3: 0 1 5 4 3
Merge # 4: 0 1 5 3 4
Merge # 5: 0 1 3 4 5
I need it to run for 20 integers and i don't know how to begin. I know to use the merge sort algorithm but thats it.
-
You need to apply mergesort to the array, since you already know how to do that, you only need to implement it. So your recursive function could contain the recursion step, the end step and a print function to print the actual state of the array.
Assuming you know the basics of C programming I would suggest to design the program, implement it and then test it. If it doesn't work try to find the error and if there are still questions after a while, post your code and question.
-
This is what i have so far:
#include <stdio.h>
#include <stdlib.h>
#define MAX 200
int factorial(int n);
void input();
void merge_sort(int sort[], int first, int last);
void move(int list1[], int first1, int last1, int list2[], int first2);
void merge(int list[], int first1, int last1,
int first2, int last2);
int main(void)
{
some code
return 0;
}
void merge_sort(int sort[], int first, int last)
{
if(first < last) {
merge_sort( sort, first, (first+last)/2);
merge_sort( sort, (first+last)/2 + 1, last);
merge(sort, first, (first+last)/2, (first+last)/2 + 1, last);
}
}
void merge(int lists[], int first1, int last1,
int first2, int last2)
{
int temp[MAX];
int index, index1, index2;
int num;
index = 0;
index1 = first1;
index2 = first2;
num = last1 - first1 + last2 - first2 + 2;
/* while there are still elements in both lists,
* put the smallest element in the temporary array.
*/
while((index1 <= last1) && (index2 <= last2)) {
if(lists[index++] < lists[index2])
temp[index++] = lists[index1++];
else
temp[index++] = lists[index2++];
}
/* after one list is empty, fill the temporary array
* with the remaining elements in the other list.
*/
if(index1 > last1)
move(lists, index2, last2, temp, index);
else
move(lists, index1, last1, temp, index);
/* copy the list to original array */
move(temp, 0, num-1,lists, first1);
}
void move(int list1[], int first1, int last1, int list2[], int first2)
{
while(first1 <= last1)
list2[first2++] = list1[first1++];
}
I get segmentation fault what is wrong?
-
-
