merge sort

first of all recursive sucks :)
second

Code:

---

/#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("&#37;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");
        getchar();
        getchar();
        getchar();
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];
        }

        //mergeSort( leftArr, leftSize, temp );

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

---

Mergesort() will get passed just two int's, low and high indicies. (and with non global arrays, one pointer for each of them).

Merge() will get passed three low, high, and midpoint indicies. (and again, with non global arrays, one pointer for each of them).

The helper array can be used to do all the sorting, and just copy it back to the main array.

Mooon, make it easy for yourself, and make the array just 5 elements in size. And fill the array with numbers, so you won't have to keep adding them in manually, each time you want to test it out.

Save you a bundle of time.

Also these variables should go:

Code:

---

int  leftArr[100] = {0}, rightArr[100] = {0}, rightSize,leftSize

---

And I don't mean to confuse you, (but I will anyway), but there's no sorting done in the function mergesort(). :)

No, I'm not kidding. :O)

Mergesort is the "driver" recursive function, and only has a maybe 20 lines of code in it, and sorts nothing.

Just remember that merge() will do the sorting, and remove bubblesort from mergesort().

Code:

---

Mergesort() (int low, int hi) 
 
  if low < hi  {
      mid = (low + hi) /2    /* integer division */
      Mergesort(low, mid)  /* solve the lower half */
      /* now code the "solve the upper half, here */
      /* now merge the whole thing together with a call to merge(), not mergesort(). */
  }

---

Code:

---

Merge(int low, int mid, int hi)

  /* copy to temp[] */
  for (i = low  i<= hi  i++)
      temp[i] = array[i]

  i = low
  j = mid + 1
  k = low

  while( i <= mid, && j <= hi ) 
      if (temp[i] <= temp[j]
          array[k++] = temp[i++]
      else
          array[k++] = temp[j++]

---

and then a while loop does the write back to the array, from temp, in sorted order. You'll use your bubblesort here. General idea of the while loop is posted above. At the end of the while loop, if i < m then you may need to just copy the remaining elements of temp, back to array[].

Quote:

---

Originally Posted by Adak

Mergesort() will get passed just two int's, low and high indicies.
Merge() will get passed three low, high, and midpoint indicies.
(besides the array's if not global)

The helper array can be used to do all the sorting, and just copy it back to the main array. It's an odd way of doing it, but it should work (I've never done it like this though).

---

i cant change the signature of my function, so I cant use low,high and mid.
I think I need to do as laserlight suggested. I need to copy half of the array to the temp array, sort it and copy it to left_array. then copy the other half to the temp array and sort it again and copy it to right_array, and then I have two sorted array that I can merge
but implement it, thats another story :(

Quote:

---

Originally Posted by moooon

i cant change the signature of my function, so I cant use low,high and mid.
I think I need to do as laserlight suggested. I need to copy half of the array to the temp array, sort it and copy it to left_array. then copy the other half to the temp array and sort it again and copy it to right_array, and then I have two sorted array that I can merge
but implement it, thats another story :(

---

What laserlight suggested is EXACTLY what Mergesort does, as I've written it here, for you. EXACTLY

The only difference is that I've never used bubblesort in a Mergesort algorithm.

It sorts the lower half of the array, by recursively shrinking it down to just two numbers, and merging them, and then "popping back" (returning), to merge the rest of the numbers, in ever larger groups. Then it does the same for the upper half of the array, the same way. Finally, it merges these two halves, together. AND IT ONLY USES TWO ARRAYS!

You do NOT need a left[] and a right[] array. You USE TEMP ARRAY to sort it, and the ARRAY[] to hold it when it's done.

< Me smacks you gently on the back of the head >

Also, your assignment does NOT allow three arrays. Just two.

Stubborn, this one! :)

Mooon, try this:

Take a few small pieces of paper, and write some small unordered integers on them. Now, follow the code I've posted, starting with Mergesort(), and see if you can sort the pieces of paper's numbers, into their proper order.

If you can't do something by hand, it's a witch writing a program that will do it. You have to have a pretty good idea of what you're doing, first.

ok, I will give it a try
thanks for the help :)

You need to start by assuming you have finished mergeSort and merge functions, and all you need to do is call them with the right parameters.
Delete all of what you've written for mergeSort and start over. Your merge looks okay.
Okay, so you're writing mergeSort. Pretend that you already have a working mergeSort, and that for some reason it will only cope with just over half the number of items than the function your writing must cope with.
So, call that one with both halves of your array. Now call merge to join those together into one sorted array. Except that you need somewhere to put it (the last parameter to merge) so pass that temp array and lets put it there for now. Then when it's done we'll just copy the tamp array back over 'Array'.
Lastly, make sure you check for an array so small that you don't even need to do anything in the first place.
Boom, that's the mergeSort function done. About 10 lines of code written.

Note that the extra copying can be avoided by doing a four-way 'merge and merge-back' instead. But that's an optional step for after you get it working and understand it.

This is what I use for my main() in a mergesort program that's different than your needs, but it should give you some tips:

Code:

---

/* declarations */
void merge(int *, int *, int, int, int);
void PrintIt(int *, int, int);

int main(void)  {
  char ch;
  int A[] = {6, 0, 2, 9, 5, 7, 8, 4, 1, 3};
  int B[10];
  int n;
  n = sizeof(A) /sizeof(A[0]);

  printf("\n\n Before Sorting: ");
  PrintIt(A, 0, n - 1);
 
  mergesort(A, B, 0, n - 1);
 
  printf("\n\n After  Sorting: ");
  PrintIt(A, 0, n - 1);

  printf("\n\n\n Program Finished - Hit Enter to Exit");
  ch = getchar();
  return 0;
}

void PrintIt(int A[], int lo, int hi)  {
  int i;
  for(i = lo; i <= hi; i++)
      printf(" &#37;d", A[i]);
}

---

Explicitly putting numbers in A[], rather than entering them each time while you test it, is a big time & boredom, saver. You might want to malloc the temp array B[], to the size of n. Here, A[] and B[] are always of equal size, on every recursion. It's the lo, hi, and m index numbers that determine what will be worked on in the next recursive call, or return from it.

thanks alot :)
i'm trying to fix my code but so far things are not going so great
if you can post some of the mergesort code, it would be helpful
but thanks anyway

Code:

---


#include <stdio.h>

/* declarations */
void merge(int *, int *, int, int, int);
void PrintIt(int *, int, int);


void mergesort(int *A, int *B, int lo, int hi) {
  int m;
  if (lo < hi) {
      m = (lo + hi) /2;
      mergesort(A, B, lo, m);
      /* PrintIt(A, lo, m);  */
      mergesort(A, B, m + 1, hi);
      merge(A, B, lo, m, hi);
  }
}

/* First, index m in the middle between lo and hi is determined. Then the
first part of the sequence (from lo to m) and the second part (from m+1
to hi) are sorted by recursive calls of mergesort. Then the two sorted halves
are merged by merge(). Recursion stops when lo = hi, when there will be
just one element.
*/

void merge(int A[], int B[], int lo, int m, int hi)
{
    int i, j, k;

    /* copy A to temp array B */
    for (i = lo; i <= hi; i++)
        B[i] = A[i];

    i = lo; j = m + 1; k = lo;
    /* copy back to A */
    while (i <= m && j <= hi)
        if (B[i] <= B[j])
          A[k++] = B[i++];
        else
          A[k++] = B[j++];

    /* copy back remaining elements of first half (if any)  */
    while (i <= m)
        A[k++] = B[i++];
}
/*Merge() does most of the work in Mergesort. The two halves are first copied
into an extra array, B. Now both halves are checked by the indicies i and
j, and the next number is copied back to array A, each time through the
while loop of merge();
*/


int main(void)  {
  char ch;
  int A[] = {6, 0, 2, 9, 5, 7, 8, 4, 1, 3};
  int B[10];
  int n;
  n = sizeof(A) /sizeof(A[0]);

  printf("\n\n Before Sorting: ");
  PrintIt(A, 0, n - 1);
  mergesort(A, B, 0, n - 1);
  printf("\n\n After  Sorting: ");
  PrintIt(A, 0, n - 1);

  printf("\n\n\n Program Finished - Hit Enter to Exit");
  ch = getchar();
  return 0;
}
void PrintIt(int A[], int lo, int hi)  {
  int i;
  for(i = lo; i <= hi; i++)
    printf(" &#37;d", A[i]);

}

---

This isn't fully tested code, so no guarantees. Hadn't looked at Mergesort too much, because I had an old trusty Quicksort , that I had coded up a file merger for. Anything really big got that program.

I wouldn't be posting up this whole program, except that it appears Mergesort has several variations to itself - and I couldn't find a single one that matched up with your assignment's requirements.

Quote:

---

first of all recursive sucks

---

@mooon,
I guess it would suck if it was trashing the stack. That's what your code was doing. I've made a few changes to your code. It's your responsibility to thoroughly test it.

Code:

---

#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 main(void)
{
        int n, i;
        int Array[100] = {0};

        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);
        for(i=0;i<n;i++)
        {
                printf("%d ",Array[i]);
        }
        printf("\n");
        getchar();
        getchar();
        getchar();
        return 0;
}

void mergeSort( int *pArray, int n)
{
        int  leftArr[100] = {0}, rightArr[100] = {0}, rightSize,leftSize, i;

        if (n < 2)
                return;

        leftSize = n / 2;
        rightSize = n - leftSize;
        for (i=0; i < leftSize; i++)
                leftArr[i] =  *(pArray+i);

        for (i=0; i < rightSize; i++)
                rightArr[i] = *(pArray+i+leftSize);
        mergeSort(leftArr, leftSize);
        mergeSort(rightArr, rightSize);
        merge(leftArr, leftSize, rightArr, rightSize, pArray);
}

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

---

Quote:

---

Originally Posted by BobS0327

@mooon,
I guess it would suck if it was trashing the stack. That's what your code was doing. I've made a few changes to your code. It's your responsibility to thoroughly test it.

---

He cannot change the function prototype, and cannot use other arrays, and there are very good reasons for these restrictions. If I was setting the assignment I would place the same restrictions.

Trust me, the best thing you can do is throw away the entire body of mergeSort and start over. Follow through my previous post. It contains all the instructions you need to implement a propper working solution. BobS0327 isn't too far off though.

btw it makes no difference whether you copy the data into the temp array first and merge back, or merge to the temp array, and then copy back. I'd suggest the later though as it forces you to realise that you can treat the single array as two arrays, where one of them starts at the middle. E.g.

Code:

---

int *firstUnsortedPortion = Array;
int *secondUnsortedPortion = &Array[mid];

---

first of all, BobS0327 thanks for your help but unfortunately I cant use it :(
second, iMalc your instructions seem to be fine in my head but not to the compiler
i'll give it another try...I must be missing something