Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   merge sort (http://www.velocityreviews.com/forums/t564264-merge-sort.html)

mooon33358@gmail.com 12-28-2007 08:16 AM

merge sort
 
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 12-28-2007 08:59 AM

Re: merge sort
 
mooon33358@gmail.com 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

mooon33358@gmail.com 12-28-2007 10:16 AM

Re: merge sort
 
On Dec 28, 10:59*am, Richard Heathfield <r...@see.sig.invalid> wrote:
> mooon33...@gmail.com 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 12-28-2007 10:45 AM

Re: merge sort
 
mooon33358@gmail.com said:

> On Dec 28, 10:59 am, Richard Heathfield <r...@see.sig.invalid> wrote:
>> mooon33...@gmail.com 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.
>>

<snip>
>
> 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.

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

user923005 12-28-2007 08:34 PM

Re: merge sort
 
On Dec 28, 12:16*am, mooon33...@gmail.com wrote:
> 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 news:comp.programming and some of the regulars
will tell you where you went off.
Follow-ups set.

steve.pagliarulo@gmail.com 12-28-2007 09:24 PM

Re: merge sort
 
On Dec 28, 12:16*am, mooon33...@gmail.com wrote:
> 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 12-28-2007 10:17 PM

Re: merge sort
 
mooon33358@gmail.com wrote:
>
> 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)

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee, Frohe Weihnachten
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>



--
Posted via a free Usenet account from http://www.teranews.com


mooon33358@gmail.com 12-28-2007 10:22 PM

Re: merge sort
 
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[i]);
}

mergeSort( Array, n, temp );
for(i=0;i<n;i++)
{
printf("%d ",Array[i]);
}
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[i] = Array[i];
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (temp[i] > temp[j]) { /*swap:*/
temp_int = temp[i];
temp[i] = 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[i] = Array[i];


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



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

temp_Size = rightSize;

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

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

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

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[i] < rightArr[j] )
{
sortArr[k] = leftArr[i];
i++;
k++;
}
else
{
sortArr[k] = rightArr[j];
j++;
k++;
}

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


}

user923005 12-29-2007 04:36 AM

Re: merge sort
 
On Dec 28, 2:22*pm, mooon33...@gmail.com wrote:
> 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[i]);
> * * * * }
>
> * * * * mergeSort( Array, n, temp );
> * * * * for(i=0;i<n;i++)
> * * * * {
> * * * * * * * * printf("%d ",Array[i]);
> * * * * }
> * * * * 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[i] = Array[i];
> * * * * for (i=0; i<n-1; i++)
> * * * * * * * * for (j=i+1; j<n; j++)
> * * * * * * * * * * * * if (temp[i] > temp[j]) { */*swap:*/
> * * * * * * * * * * * * * * * * temp_int = temp[i];
> * * * * * * * * * * * * * * * * temp[i] = 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[i] = Array[i];
>
> * * * * for( i = 0; i < temp_Size; i++ )
> * * * * {
> * * * * * * * * temp[i] = Array[i];
> * * * * }
>
> * * * * for( i = 0; i < temp_Size; i++ )
> * * * * {
> * * * * * * * * leftArr[i] = temp[i];
> * * * * }
>
> * * * * temp_Size = rightSize;
>
> * * * * for( i = 0; i < temp_Size; i++ )
> * * * * {
> * * * * * * * * temp[i] = Array[leftSize+i];
> * * * * }
>
> * * * * for (i=0; i<n-1; i++)
> * * * * * * * * for (j=i+1; j<n; j++)
> * * * * * * * * * * * * if (temp[i] > temp[j]) { */*swap:*/
> * * * * * * * * * * * * * * * * temp_int = temp[i];
> * * * * * * * * * * * * * * * * temp[i] = temp[j];
> * * * * * * * * * * * * * * * * temp[j] = temp_int;
> * * * * * * * * * * * * } /* end of if */
>
> * * * * * * * * * * * * mergeSort( rightArr, rightArr, temp );
> * * * * for( i = 0; i < temp_Size; i++ )
> * * * * * * * * rightArr[i] = temp[i];
>
> * * * * *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[i] < rightArr[j] )
> * * * * * * * * {
> * * * * * * * * * * * * sortArr[k] = leftArr[i];
> * * * * * * * * * * * * i++;
> * * * * * * * * * * * * k++;
> * * * * * * * * }
> * * * * * * * * else
> * * * * * * * * {
> * * * * * * * * * * * * sortArr[k] = rightArr[j];
> * * * * * * * * * * * * j++;
> * * * * * * * * * * * * k++;
> * * * * * * * * }
>
> * * * * }
> * * * * while(i<leftSize)
> * * * * {
> * * * * * * * * sortArr[k]= leftArr[i];
> * * * * * * * * 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 01-02-2008 09:21 PM

Re: merge sort
 
mooon33358@gmail.com wrote:
>
> 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 */

--
pete


All times are GMT. The time now is 06:48 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.