Just a question

[sj]

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)
{
int i, half1, half2;
char arr1[MAX/2+1];
char arr2[MAX/2+1];
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);

int x2 = msort(arr2, half2);

if( list[x1] > list[x2]) return x1;
else
return x2;
}
}

int main()
{
int i, n;
char array[MAX];
n = 7;

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 );

printf("\n");
return 0;
}

what am i doing wrong here?
thanks for any help

sj

[Michael Mair]

Re: Just a question



sj wrote:[color=blue]
> 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)[/color]
I would rather call this function index_of_max or something
like that and use size instead of n.[color=blue]
> {
> int i, half1, half2;
> char arr1[MAX/2+1];
> char arr2[MAX/2+1];[/color]
(*) C90 style declarations[color=blue]
> 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);[/color]
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.[color=blue]
>
> int x2 = msort(arr2, half2);[/color]
This is the relative index with respect to arr2. The
index w.r.t list would be x2+half1.[color=blue]
>
> if( list[x1] > list[x2]) return x1;[/color]
(**)
Here you compare the wrong list-element. Either set
x2 = msort(arr2, half2) + half1;
above or compare list[x1] with list[x2+half1] here.[color=blue]
> else
> return x2;
> }
> }
>
> int main()[/color]
Rather use
int main (void)[color=blue]
> {
> int i, n;
> char array[MAX];
> n = 7;[/color]
This would be n=MAX;[color=blue]
>
> 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 );[/color]
For better control, I'd output x and array[x].[color=blue]
>
> printf("\n");
> return 0;
> }
>
> what am i doing wrong here?
> thanks for any help[/color]

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(li st, half);
index2 = half + index_of_max(&l ist[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(ar ray, n);

printf("index of maximal element: %zu (--> %c)\n",
index, array[index]);

return 0;
}

--
E-Mail: Mine is a gmx dot de address.

[Nick Austin]

Re: Just a question

On 6 Nov 2004 07:39:24 -0800, kpsj2002@yahoo. com (sj) wrote:
[color=blue]
>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)
>{
> int i, half1, half2;
> char arr1[MAX/2+1];
> char arr2[MAX/2+1];
> 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);
>
> int x2 = msort(arr2, half2);
>
> if( list[x1] > list[x2]) return x1;
> else
> return x2;[/color]

You copied the array, so arr2[x2] is actually
list[half2+x2]. Therefore this return should
be:

return half2+x2;
[color=blue]
> }
>}[/color]

Nick.

[Simon Richard Clarkstone]

Re: Just a question

sj wrote:[color=blue]
> Hi;
> I am trying to find the position of the maximum element of and array using
> divide-and-conquer method.[/color]
....[color=blue]
> what am i doing wrong here?[/color]

This is an odd algorithm to use unless:
a) It's homework (okay to ask since you have shown us some effort)
b) You are practising your skills or some similar thing (good)
c) You are going to adapt it to run in several threads (i.e. you are
splitting the task into unordered subtasks so that it will run faster
(probably O(log(n)))
I you have a good reason to use this algorithm (like those) then ignore
the rest is this.

* If the array is sorted (I assume it isn't here), then the maximum is
at one end.
* If the array is unsorted, then the best algorithm is simply a linear
search (unless condition "c)" above applies). This is because the
maximum could be any of the elements, so you have to compare all of them
to something, and that is an O(n) algorithm.
* Just about anything else will be slower, unless the array is known to
have some strange pattern without being sorted. If the maximum element
is likely to be in a certain place, then start there.

For algorithm discussion, check out comp.programmin g (follow-ups set).

--
Simon Richard Clarkstone
s.r.cl*rkst*n*@ durham.ac.uk / s*m*n_cl*rkst*n *@hotmail.com