merge sort

[mooon33358]

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array,
its size, and an help array(i.e mergesort(int [] array, int size,
int[] temp] . I have to use only the temp array for the sorting, I
cant use two help arrays for the sorting, and I cant change the
signature of the function.
also have a merge function that takes 5 arguments - left array and its
size, right array and its size, and final array.
I dont have a problem with the merge function only with the mergesort.
can someone post the code for it?

 

[Richard Heathfield]

(e-mail address removed) said:

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array,
its size, and an help array(i.e mergesort(int [] array, int size,
int[] temp] .

That ain't ever gonna compile.

I have to use only the temp array for the sorting, I
cant use two help arrays for the sorting, and I cant change the
signature of the function.
also have a merge function that takes 5 arguments - left array and its
size, right array and its size, and final array.
I dont have a problem with the merge function only with the mergesort.
can someone post the code for it?

"Merging (or collating) means the combination of two or more ordered files
into a single ordered file." (Knuth)

(For "file", we can read "array" if we prefer.)

This is indeed the easy part, and I will presume that you have no problem
with it. The difficult bit is getting the two ordered arrays in the first
place!

But this turns out not to be so hard. To mergesort an array, simply split
your unordered array into two parts, and mergesort them both (unless of
course they are already in order), and then merge them (which you say you
already know how to do).

 

[mooon33358]

(e-mail address removed) said:

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array,
its size, and an help array(i.e mergesort(int [] array, int size,
int[] temp] .

That ain't ever gonna compile.

I have to use only the temp array for the sorting, I
cant use two help arrays for the sorting, and I cant change the
signature of the function.
also have a merge function that takes 5 arguments - left array and its
size, right array and its size, and final array.
I dont have a problem with the merge function only with the mergesort.
can someone post the code for it?

"Merging (or collating) means the combination of two or more ordered files
into a single ordered file." (Knuth)

(For "file", we can read "array" if we prefer.)

This is indeed the easy part, and I will presume that you have no problem
with it. The difficult bit is getting the two ordered arrays in the first
place!

But this turns out not to be so hard. To mergesort an array, simply split
your unordered array into two parts, and mergesort them both (unless of
course they are already in order), and then merge them (which you say you
already know how to do).

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

why do you think it won't compile? thats the exercise
and can you post a sample from the code of my mergesort?

 

[Richard Heathfield]

(e-mail address removed) said:

(e-mail address removed) said:

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array,
its size, and an help array(i.e mergesort(int [] array, int size,
int[] temp] .

That ain't ever gonna compile.

why do you think it won't compile? thats the exercise

Partly because int [] array isn't a legal description of a parameter to a
function, and partly because ] isn't a legal way to close a function
parameter list. You probably meant to write:

int mergesort(int array[], int size, int temp[])

and can you post a sample from the code of my mergesort?

I'd be delighted to post a sample from your mergesort code, if you'd be so
good as to tell me where you have placed it and how I can gain access to
that place.

 

[user923005]

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array,
its size, and an help array(i.e mergesort(int [] array, int size,
int[] temp] . I have to use only the temp array for the sorting, I
cant use two help arrays for the sorting, and I cant change the
signature of the function.
also have a merge function that takes 5 arguments - left array and its
size, right array and its size, and final array.
I dont have a problem with the merge function only with the mergesort.
can someone post the code for it?

Post your attempt in and some of the regulars
will tell you where you went off.
Follow-ups set.

 

[steve.pagliarulo]

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array,
its size, and an help array(i.e mergesort(int [] array, int size,
int[] temp] . I have to use only the temp array for the sorting, I
cant use two help arrays for the sorting, and I cant change the
signature of the function.
also have a merge function that takes 5 arguments - left array and its
size, right array and its size, and final array.
I dont have a problem with the merge function only with the mergesort.
can someone post the code for it?

Why are we merging? Any in-place sort will do without the use of the
help array. And there are other out-of-place sort routines that can
use the help array.

 

[CBFalconer]

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an
array, its size, and an help array(i.e mergesort(int [] array, int
size, int[] temp] . I have to use only the temp array for the
sorting, I cant use two help arrays for the sorting, and I cant
change the signature of the function. also have a merge function
that takes 5 arguments - left array and its size, right array and
its size, and final array. I dont have a problem with the merge
function only with the mergesort. can someone post the code for it?

If the array is not essential, see about making the sorted item a
singly linked list. For such, there is adequate mergesort code in
the demonstration uses for hashlib. Lists are intrinsically
unlimited (apart from machine resources) as to size. Mergesort
uses minimal extra storage. See:

<http://cbfalconer.home.att.net/download/> (for hashlib)

 

[mooon33358]

here is my code
my problem is the mergesort function
what I need to write there?

#include <stdio.h>
#include <stdlib.h>

void merge(int *leftArr, int leftSize, int *rightArr, int rightSize,
int *sortArr);
void mergeSort( int *Array, int n, int *temp );

int main()
{
int n , Array[100] , temp[100] ;
int i ;

scanf("%d", &n);


if( ( n <= 0 ) || ( n > 100 ) )
{
printf("error!\n");
return -1;
}
for( i = 0; i < n; i++ )
{
scanf("%d", &Array);
}

mergeSort( Array, n, temp );
for(i=0;i<n;i++)
{
printf("%d ",Array);
}
printf("\n");

return 0;
}

void mergeSort( int *Array, int n, int *temp )
{
int leftArr[100] = {0}, rightArr[100] = {0},
rightSize,leftSize,temp_Size;
int i,j,temp_int;



if (n < 2)
return;

for (i=0; i<n; i++) temp = Array;
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (temp > temp[j]) { /*swap:*/
temp_int = temp;
temp = temp[j];
temp[j] = temp_int;
} /* end of if */


leftSize = n/2;
rightSize = n - leftSize;
mergeSort( leftArr, leftSize, temp );


temp_Size = leftSize;
for( i = 0; i < leftSize; i++ )
leftArr = Array;


for( i = 0; i < temp_Size; i++ )
{
temp = Array;
}



for( i = 0; i < temp_Size; i++ )
{
leftArr = temp;
}

temp_Size = rightSize;

for( i = 0; i < temp_Size; i++ )
{
temp = Array[leftSize+i];
}

for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (temp > temp[j]) { /*swap:*/
temp_int = temp;
temp = temp[j];
temp[j] = temp_int;
} /* end of if */

mergeSort( rightArr, rightArr, temp );
for( i = 0; i < temp_Size; i++ )
rightArr = temp;

mergeSort( rightArr, rightSize, temp );

merge( leftArr, leftSize, rightArr, rightSize, Array );
}
/* This function merges both sub arrays */

void merge(int *leftArr, int leftSize, int *rightArr, int rightSize,
int *sortArr)
{
int i =0, j = 0, k = 0;


while ( ( i < leftSize )&& ( j < rightSize ) )
{
if ( leftArr < rightArr[j] )
{
sortArr[k] = leftArr;
i++;
k++;
}
else
{
sortArr[k] = rightArr[j];
j++;
k++;
}

}
while(i<leftSize)
{
sortArr[k]= leftArr;
i++;
k++;
}
while(j<rightSize)
{
sortArr[k]= rightArr[j];
j++;
k++;
}


}

 

[user923005]

here is my code
my problem is the mergesort function
what I need to write there?

#include <stdio.h>
#include <stdlib.h>

void merge(int *leftArr, int leftSize, int *rightArr, int rightSize,
int *sortArr);
void mergeSort( int *Array, int n, int *temp );

int main()
{
        int n , Array[100] , temp[100] ;
        int i ;

        scanf("%d", &n);

        if( ( n <= 0 ) ||  ( n > 100 ) )
        {
                printf("error!\n");
                return -1;
        }
        for( i = 0; i < n; i++ )
        {
                scanf("%d", &Array);
        }

        mergeSort( Array, n, temp );
        for(i=0;i<n;i++)
        {
                printf("%d ",Array);
        }
        printf("\n");

return 0;

}

void mergeSort( int *Array, int n, int *temp )
{
        int  leftArr[100] = {0}, rightArr[100] = {0},
rightSize,leftSize,temp_Size;
        int i,j,temp_int;

        if (n < 2)
                return;

        for (i=0; i<n; i++) temp = Array;
        for (i=0; i<n-1; i++)
                for (j=i+1; j<n; j++)
                        if (temp > temp[j]) {  /*swap:*/
                                temp_int = temp;
                                temp = temp[j];
                                temp[j] = temp_int;
                        } /* end of if */

        leftSize = n/2;
        rightSize =  n - leftSize;
        mergeSort( leftArr, leftSize, temp );

        temp_Size = leftSize;
        for( i = 0; i < leftSize; i++ )
                leftArr = Array;

        for( i = 0; i < temp_Size; i++ )
        {
                temp = Array;
        }

        for( i = 0; i < temp_Size; i++ )
        {
                leftArr = temp;
        }

        temp_Size = rightSize;

        for( i = 0; i < temp_Size; i++ )
        {
                temp = Array[leftSize+i];
        }

        for (i=0; i<n-1; i++)
                for (j=i+1; j<n; j++)
                        if (temp > temp[j]) {  /*swap:*/
                                temp_int = temp;
                                temp = temp[j];
                                temp[j] = temp_int;
                        } /* end of if */

                        mergeSort( rightArr, rightArr, temp );
        for( i = 0; i < temp_Size; i++ )
                rightArr = temp;

         mergeSort( rightArr, rightSize, temp );

        merge( leftArr, leftSize, rightArr, rightSize, Array );}

/* This function merges both sub arrays */

void merge(int *leftArr, int leftSize, int *rightArr, int rightSize,
int *sortArr)
{
        int i =0, j = 0, k = 0;

        while ( ( i < leftSize )&& (  j < rightSize ) )
        {
                if ( leftArr < rightArr[j] )
                {
                        sortArr[k] = leftArr;
                        i++;
                        k++;
                }
                else
                {
                        sortArr[k] = rightArr[j];
                        j++;
                        k++;
                }

        }
        while(i<leftSize)
        {
                sortArr[k]= leftArr;
                i++;
                k++;
        }
        while(j<rightSize)
        {
                sortArr[k]= rightArr[j];
                j++;
                k++;
        }



}

Your merge() is fine {if a bit verbose} but your mergesort is not even
close.

 

[pete]

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array,
its size, and an help array(i.e mergesort(int [] array, int size,
int[] temp] . I have to use only the temp array for the sorting, I
cant use two help arrays for the sorting, and I cant change the
signature of the function.
also have a merge function that takes 5 arguments - left array and its
size, right array and its size, and final array.
I dont have a problem with the merge function only with the mergesort.
can someone post the code for it?

/* BEGIN mergesort.c */

void mergesort(int array[], int size, int temp[])
{
if (size > 1) {
int *mid_ptr;
int const half = size / 2;
int *const after_buff = temp + half;
int *const middle = array + half;
int *const after_array = array + size;

mergesort(middle, size - half, temp);
mergesort(array, half, temp);
do {
if (*array > *middle) {
mid_ptr = middle;
temp = after_buff;
do {
*--temp = *--mid_ptr;
} while (array != mid_ptr);
mid_ptr = middle;
*array++ = *mid_ptr++;
while (middle != array) {
*array++ = *(*temp > *mid_ptr
? mid_ptr++ : temp++);
}
while (after_buff != temp) {
if (after_array != mid_ptr) {
*array++ = *(*temp > *mid_ptr
? mid_ptr++ : temp++);
} else {
do {
*array++ = *temp++;
} while (after_buff != temp);
break;
}
}
break;
} else {
++array;
}
} while (middle != array);
}
}

/* END mergesort.c */