sj wrote:
Hi;
I am trying to find the position of the maximum element of and array using
divide-and-conquer method. Following is the code I am trying.
#include <stdio.h>
#define MAX 7
int msort(char list[], int n)
I would rather call this function index_of_max or something
like that and use size instead of n. {
int i, half1, half2;
char arr1[MAX/2+1];
char arr2[MAX/2+1];
(*) C90 style declarations if(n ==1) return 0;
else if (n==2){
if(list[0]>list[1]) return 0;
else return 1;
}else
{
half1 = n / 2;
half2 = n - half1;
for(i = 0; i < half1; i++)
arr1[i] = list[i];
for(i = 0; i < half2; i++)
arr2[i] = list[half1 + i];
int x1 = msort(arr1, half1);
C99 style declarations (not at the beginning of the block);
if you really use C99, then make (*) rather
char arr1[n/2+1], arr2[n/2+1];
to save memory. See below for a better solution.
int x2 = msort(arr2, half2);
This is the relative index with respect to arr2. The
index w.r.t list would be x2+half1.
if( list[x1] > list[x2]) return x1;
(**)
Here you compare the wrong list-element. Either set
x2 = msort(arr2, half2) + half1;
above or compare list[x1] with list[x2+half1] here. else
return x2;
}
}
int main()
Rather use
int main (void) {
int i, n;
char array[MAX];
n = 7;
This would be n=MAX;
array[0] = 'A';
array[1] = 'B';
array[2] = 'C';
array[3] = 'D';
array[4] = 'E';
array[5] = 'F';
array[6] = 'X';
int x = msort(array, n);
printf("%d ", x );
For better control, I'd output x and array[x].
printf("\n");
return 0;
}
what am i doing wrong here?
thanks for any help
It is not necessary to copy all the stuff from list to arr1 and
arr2. If you insist, rather use memcpy().
I would propose that you pass on &list[0] and &list[half1] directly
because list is not modified in msort().
In order to document this, use the const qualifier for the declaration
of list.
However, only the changes suggested in (**) are necessary, to make
your program run.
As I had some time on my fingers, I have rewritten parts of your
program and did some things deliberately different; maybe this is
useful for you.
Note: I use size_t instead of int because then I am sure that
the range of the indices fits every char array which can be stored
in memory.
Cheers
Michael
--------
#include <stdio.h>
#define MAX 7
size_t index_of_max (const char *list, size_t listsize)
{
size_t half, index1, index2;
switch (listsize) {
case 0:
fprintf(stderr, "%s: invalid size of list (0)\n",
__func__);
return 0;
case 1:
return 0;
case 2:
index1 = 0; index2 = 1;
break;
default:
half = listsize / 2;
index1 = index_of_max(list, half);
index2 = half + index_of_max(&list[half], listsize-half);
}
if (list[index1] > list[index2])
return index1;
else
return index2;
}
int main (void)
{
size_t n, index;
char array[MAX];
n = MAX;
array[0] = 'A';
array[1] = 'B';
array[2] = 'C';
array[3] = 'D';
array[4] = 'E';
array[5] = 'F';
array[6] = 'X';
index = index_of_max(array, n);
printf("index of maximal element: %zu (--> %c)\n",
index, array[index]);
return 0;
}
--
E-Mail: Mine is a gmx dot de address.
