merge sort

Discussion in 'C Programming' started by mooon33358@gmail.com, Dec 28, 2007.

  1. Guest

    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?
    , Dec 28, 2007
    #1
    1. Advertising

  2. 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
    Richard Heathfield, Dec 28, 2007
    #2
    1. Advertising

  3. Guest

    On Dec 28, 10:59 am, Richard Heathfield <> wrote:
    > 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?
    , Dec 28, 2007
    #3
  4. said:

    > On Dec 28, 10:59 am, Richard Heathfield <> wrote:
    >> 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
    Richard Heathfield, Dec 28, 2007
    #4
  5. user923005 Guest

    On Dec 28, 12:16 am, 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.
    user923005, Dec 28, 2007
    #5
  6. Guest

    On Dec 28, 12:16 am, 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.
    , Dec 28, 2007
    #6
  7. CBFalconer Guest

    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
    CBFalconer, Dec 28, 2007
    #7
  8. Guest

    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];
    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++;
    }


    }[/i][/i]
    , Dec 28, 2007
    #8
  9. user923005 Guest

    On Dec 28, 2:22 pm, 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);
    >         }
    >
    >         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[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++;
    >         }
    >
    >
    >
    > }[/i][/i][/i]
    [i][i]

    Your merge() is fine {if a bit verbose} but your mergesort is not even
    close.[/i][/i]
    user923005, Dec 29, 2007
    #9
  10. pete Guest

    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
    pete, Jan 2, 2008
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    4,456
  2. Replies:
    1
    Views:
    960
    Jonathan Bromley
    Mar 31, 2005
  3. Seth G.

    Merge Sort question

    Seth G., Aug 11, 2003, in forum: Java
    Replies:
    10
    Views:
    1,215
    Jordan Zimmerman
    Aug 15, 2003
  4. rkk
    Replies:
    9
    Views:
    804
    CBFalconer
    Sep 24, 2006
  5. Navin
    Replies:
    1
    Views:
    672
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page