Thread: problem with sorting algorithim (using merge sort)

hello guys, so I had to write a code which sorts points(x,y) according to their distance of (0,0) point.

at first it asks for how many points will you enter? for example 3.
and then u enter the x and the y of each point
for example :

1 6
2 5
4 4

so the result should be printing the point sorted from shortest distance to longest which is : (2,5) (4,4) (1,6)

the problem in my code , for the example i gave u the output is:
(2,5) (2,5) (1,6)
I used a two dimensional array with size [n][2] .. n is the number of points, for example in
arr[0][0] the x of first point is stored
arr[0][1] the y of first point is stored
any ideas where could be the problem ? thanks

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void initiate(int array[][2],int n)
{
    for(int i=0;i<n;i++)
   {
       for(int j=0 ;j<2;j++)
       {
           array[i][j]=0;
       }
   }
}


void printarray(int TDarray[][2],int number)
{
    printf("Sorted Points:");
   for(int i=0;i<number;i++)
    {
        printf(" (%d,%d)",TDarray[i][0],TDarray[i][1]);


    }
}


void merge(int a[][2], int na, int b[][2], int nb, int c[][2])
 {
   int ia, ib, ic;
   for(ia = ib = ic = 0; (ia < na) && (ib < nb); ic++)
     {
       if((a[ia][0])*(a[ia][0]) + (a[ia][1])*(a[ia][1]) < (b[ib][0])*(b[ib][0]) + (b[ib][1])*(b[ib][1])) {
           c[ic][0] = a[ia][0];
           c[ic][1] = a[ia][1];
           ia++;
     }
       else {
           c[ic][0] = b[ia][0];
           c[ic][1] = b[ia][1];
           ib++;
       }
     }
   for(;ia < na; ia++, ic++)
   {
       c[ic][0] = a[ia][0];
       c[ic][1] = a[ia][1];
   }
   for(;ib < nb; ib++, ic++)
   {
       c[ic][0] = b[ib][0];
       c[ic][1] = b[ib][1];
   }
}


void copyarray(int a[][2],int helper_array[][2],int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<2;j++)
        {
            a[i][j]=helper_array[i][j];
        }
    }
}


void internal_msort(int a[][2], int n, int helper_array[][2])
{
    int left = (n/2), right = n-left;
    if (n < 2)
        {return;}
    internal_msort(a, left, helper_array);
    internal_msort(a + left, right, helper_array);
    merge(a, left, a + left, right, helper_array);
    copyarray(a, helper_array, n);


}


void merge_sort(int a[][2], int n)
{
   int helper_array[n][2];
   initiate(helper_array,n);
   internal_msort(a, n,helper_array);
   printarray(a,n);
}


int main()
{
    int number;
    printf("Enter number of points: ");
    scanf("%d",&number);
    int TDarray[number][2];
    initiate(TDarray,number);
    for(int i=0;i<number;i++)
    {
        printf("Enter Point: ");
        for(int j=0;j<2;j++)
        {
        scanf("%d",&TDarray[i][j]);
        }
    }
    merge_sort(TDarray,number);
  return 0;
}

Consider n == 10. Then here

Code:

int left = (n/2), right = n-left;

you're setting both left and right to 5.

In general, that line sets left and right to n/2 if n is even and to n/2 and n/2+1, respectively, if n is odd.

Try something along the lines of:

Code:

   middle = (right + left) / 2; // or (right-left)/2+left to avoid overflow
   msort from left to middle
   msort from middle+1 to right
   merge left to middle, middle+1 to right

(The details depend on whether your upper bound is one-past-the-end or not.)

Originally Posted by algorism

In general, that line sets left and right to n/2 if n is even and to n/2 and n/2+1, respectively, if n is odd.

first of all thank u for responding
so u say the code doesn't work well when n is odd , okay let's give it an n=4 ,then the points will be the same as before adding (0,0) as the first one - I mean:
0 0
1 6
2 5
4 4
the output is : (0,0) (4,4) (4,4) (1,6)
although n isn't prime ! :\
what do u think my friend ?

I didn't say the code doesn't work well if n is odd. I said it doesn't work no matter what n is. I also told you how to fix it.

Are you aware that you could implement a bottom up merge instead which would skip all the recursive splitting of the array into sub-arrays? Take a look at the wiki examples on the main page and also the talk page:

http://en.wikipedia.org/?title=Merge...implementation

Is writing your own sorting routine a necessary part of this exercise? Or can you use a well-tested existing sorting routine? C already has qsort() for sorting so you don't have to reinvent the wheel (unless you're determined to reinvent it).

Originally Posted by algorism

I didn't say the code doesn't work well if n is odd. I said it doesn't work no matter what n is. I also told you how to fix it.

Originally Posted by rcgldr

Are you aware that you could implement a bottom up merge instead which would skip all the recursive splitting of the array into sub-arrays? Take a look at the wiki examples on the main page and also the talk page:

http://en.wikipedia.org/?title=Merge...implementation

algorism and rcgldr thank u very much for your help , I used the bottom up merge which does as algorism said (uses middle index) and it worked , but later i tried to find what's wrong in my previous code so here it is : (a very stupid mistake of me):
int the merge function -> first for loop -> inside else I wrote

Code:

c[ic][0] = b[ia][0];
c[ic][1] = b[ia][1];
ib++;

it should have been the index ib not ia in the b array.

Code:

c[ic][0] = b[ib]0];
c[ic][1] = b[ib][1];
ib++;

sorry guys,my mistake.

Originally Posted by christop

Is writing your own sorting routine a necessary part of this exercise? Or can you use a well-tested existing sorting routine? C already has qsort() for sorting so you don't have to reinvent the wheel (unless you're determined to reinvent it).

yes it is necessary part to use merge sort , anyway it worked now thank you

Forgot to mention, the bottom up merge sort can end up with the sorted data in a[] by calculating the number of passes needed and if the number of passes is an odd number, then the first pass swaps elements in place in a[] as needed to form runs of 2 instead of merging to b[], leaving an even number of passes remaining so the sorted data ends up in a[].