Merge sort help

[stfh]

Hello everyone. I need some help with my programm. All of my sorts works fine but merge. When i chose to sort with MergeSort i face problems, like my programm is crushing or there are trashes.

Could someone help me? I only need help for MERGESORT!

thank you!

#include <stdio.h>
#include <malloc.h>
#include <time.h>




int i,j,temp,position,n, average=0;




int main()
{


    int choise;


    do
    {
         printf(" \n\n  ---------- MENU ----------");
         printf("\n 1--> Selection Sort");
         printf("\n 2--> Insertion Sort");
         printf("\n 3--> Bubble Sort");
         printf("\n 4--> Heap Sort");
         printf("\n 5--> Merge Sort");
         printf("\n 6--> Quick Sort");
         printf("\n 0--> EXIT \n");
         scanf("%d", &choise);


         switch(choise)
         {
             case 1:
             {


                 printf("Parakalo oriste to megethos tou pinaka: \t");
                 scanf("%d", &n);


                 int *A = (int *) malloc(n * sizeof(int));


                 srand(time(NULL));
                 for (i=0; i<=n; i++)
                 {
                    A[i]= 1 + rand()%10;
                 }




                 clock_t start, end;
                 double elapsed;
                 start = clock();


                 SelectionSort(A,n);


                 end = clock();
                 elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;


                 printf("\n\n Mesos xronos SELECTION SORT :%f\n", elapsed);
                 printf("\n Mesos #oros SELECTION SORT: \t %d", average );




                 break;


             }
             case 2:
             {
                 printf("Parakalo oriste to megethos tou pinaka: \t");
                 scanf("%d", &n);


                 int *A = (int *) malloc(n * sizeof(int));


                 srand(time(NULL));
                 for (i=0; i<=n; i++)
                 {
                    A[i]= 1 + rand()%10;
                 }


                 clock_t start, end;
                 double elapsed;
                 start = clock();


                 InsertionSort(A, n);


                 end = clock();
                 elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;


                 printf("\n\n Mesos xronos INSERTION SORT :%f\n", elapsed);
                 printf("\n Mesos #oros INSERTION SORT: \t %d", average );


                 break;
             }
             case 3:
             {
                 printf("Parakalo oriste to megethos tou pinaka: \t");
                 scanf("%d", &n);


                 int *A = (int *) malloc(n * sizeof(int));


                 srand(time(NULL));
                 for (i=0; i<=n; i++)
                 {
                    A[i]= 1 + rand()%10;
                 }


                 clock_t start, end;
                 double elapsed;
                 start = clock();


                 BubbleSort(A,n);


                 end = clock();
                 elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;


                 printf("\n\n Mesos xronos BUBBLE SORT :%f\n", elapsed);
                 printf("\n Mesos #oros BUBBLE SORT: \t %d", average );


                 break;
             }
             case 4:
             {
                 printf("Parakalo oriste to megethos tou pinaka: \t");
                 scanf("%d", &n);


                 int *A = (int *) malloc(n * sizeof(int));


                 srand(time(NULL));
                 for (i=0; i<=n; i++)
                 {
                    A[i]= 1 + rand()%10;
                 }


                 clock_t start, end;
                 double elapsed;
                 start = clock();


                 HeapSort(A,n);


                 end = clock();
                 elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;


                 printf("\n\n Mesos xronos HEAP SORT :%f\n", elapsed);
                 printf("\n Mesos #oros HEAP SORT: \t %d", average );


                 break;
             }
             case 5:
             {
                 printf("Parakalo oriste to megethos tou pinaka: \t");
                 scanf("%d", &n);


                 int *A = (int *) malloc(n * sizeof(int));


                 srand(time(NULL));
                 for (i=0; i<=n; i++)
                 {
                    A[i]= 1 + rand()%10;
                 }




                 clock_t start, end;
                 double elapsed;
                 start = clock();


                 MergeSort(A, 0, n-1);


                 end = clock();
                 elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;


                 printf("\n\n Mesos xronos MERGE SORT :%f\n", elapsed);
                 //printf("\n Mesos #oros MERGE SORT: \t %d", average );


                 /*printf("\n O pinakas ta3inomimenos meta apo MERGE SORT \n\n");
                 for(i=0; i<n; i++)
                 {
                     printf("%d \t", A[i]);
                 }*/


                 free(A);
                 break;
             }
             case 6:
             {
                 printf("Parakalo oriste to megethos tou pinaka: \t");
                 scanf("%d", &n);


                 int *A = (int *) malloc(n * sizeof(int));


                 srand(time(NULL));
                 for (i=0; i<=n; i++)
                 {
                    A[i]= 1 + rand()%10;
                 }


                 clock_t start, end;
                 double elapsed;
                 start = clock();


                 QuickSort(A, 0, n-1);


                 end = clock();
                 elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;


                 printf("\n\n Mesos xronos QUICK SORT :%f\n", elapsed);
                 printf("\n Mesos #oros QUICK SORT: \t %d", average );


                 /*printf("\n O pinakas ta3inomimenos meta apo QUICK SORT \n\n");
                 for(i=0; i<n; i++)
                 {
                    printf("%d \t", A[i]);
                 }


                 free(A);*/
                 break;
             }
             case 0 :
             {
                 printf("\n--------------------------\n");
                 printf("|Eksodos apo to programma|\n");
                 printf("--------------------------\n");
                 return 0;
             }


            default:
            {
                printf("\n Edwses lathos epilogi. Ksanaprospa8ise  \n\n\n");
                continue;
            }
         }




    }while ((choise!=1) || (choise!=2));


    return 0;
}


SelectionSort (int k[] , int n)
{
    int sum1=0,sum2=0;
    for (i=n; i>0; i--)
    {
        position = 0;
        for (j =0; j<i; j++)
        {
            if(k[position] < k[j])
            {
                position = j ;
            }
            temp = k[position];
            k[position] = k[i-1];
            k[i-1] = temp;
            sum1 += 1;
        }
    }


    /*printf("\n O pinakas ta3inomimenos meta apo SELECTION SORT \n\n");
    for(i=0; i<n; i++)
    {
        printf("%d \t", k[i]);
    }*/
    average = (sum1+sum2)/ n ;


    free(k);


    return average;
}


InsertionSort(int k[],int n)
{
    int sum1=0,sum2=0;
    for (i=0; i<=n; i++)
    {
        temp = k[i];


        for (j = i-1; ((j >=0) && (temp < k[j])); j--)
        {
            k[j+1] = k[j];
            sum2 +=1 ;
        }
        k[j+1] = temp;


    }


    /*printf("\n O pinakas ta3inomimenos meta apo INSERTION SORT \n\n");
    for(i=0; i<n; i++)
    {
        printf("%d \t", k[i]);
    }*/




    free(k);


    average = sum2 / n;
    return average;
}




BubbleSort(int k[], int n)
{
    int sum1=0,sum2=0;
    for (i=0; i<(n-1); i++)
    {
        for (j=0; j< n - i -1; j++)
        {
            if (k[j] > k[j+1])
            {
                temp = k[j];
                k[j] = k[j+1];
                k[j+1] = temp;
                sum2 += 1;
            }


        }
    }


   /* printf("\n O pinakas ta3inomimenos meta apo BUBBLE SORT \n\n");
    for(i=0; i<n; i++)
    {
        printf("%d \t", k[i]);
    }*/




    free(k);


    average = sum2 / n;
    return average;
}




HeapSort(int k[], int n)
{
    int sum1=0,sum2=0;


    for (i=(n/2)-1; i>=0; i--)
    {
        fixheap(k, i, n);
        sum2+=1;
    }




    for (i=n-1; i>=1; i--)
    {
        temp = k[0];
        k[0] = k[i];
        k[i] = temp;
        fixheap(k, 0, i-1);
        sum2+=1;
    }


    /*printf("\n O pinakas ta3inomimenos meta apo HEAP SORT \n\n");
    for(i=0; i<n; i++)
    {
        printf("%d \t", k[i]);
    }*/




    free(k);


    average = sum2 / n;
    return average;
}




fixheap(int A[], int i, int N)
{
  int max, temp2 = 0;




    while ((left(i)<=N) )
    {
        if (left(i)==N)
        {
           max=left(i);


        }


        else if (A[left(i)]>A[right(i)])
        {
            max=left(i);
        }


        else
        {
            max=right(i);
        }




        if (A[i] < A[max])
        {
            temp=A[i];
            A[i]=A[max];
            A[max]=temp;
            i=max;


        }
        else
        {
            break;
        }


    }
  }




int parent (int i)
{
    return (int)(i/2);
}


int left( int i)
{
    return 2*i;
}


int right (int i)
{
    return 2*i+1;
}




MergeSort(int *k, int low, int high)
{
    int mid, sum2=0;


    if (low < high)
    {
        sum2 += 1;
        mid = (low + high) / 2 ;
        MergeSort(k, low , mid);
        MergeSort(k, mid+1, high);
        Merge(k, low, mid, high);
    }


    average = sum2 / n;
    return average;


}


Merge(int *k, int low, int mid, int high)
{
    int pin[n];
    int l,m;


    l = low;
    i = low;
    m = mid+1;


    while ( (l <=mid) && (m<=high) )
    {
        if (k[l] < k[m])
        {
            pin[i] = k[l];
            l++ ;
        }
        else
        {
            pin[i] = k[m];
            mid++;
        }


        i++;
    }


     if(l > mid)
     {
         for(j=m; j<=high; j++)
         {
             pin[i] = k[j];
             i++;
         }
    }


    else
    {
         for(j=l; j<=mid; j++)
         {
             pin[i] = k[j];
             i++;
         }
    }


    for(j=low; j<=high; j++)
    {
         k[j] = pin[j];
    }
}




QuickSort(int k[], int first, int last)
{
    int part,sum2=0;


    if (first < last)
    {
        part = first;
        i = first;
        j = last;


        while ( i < j )
        {
            while ( k[i] <= k[part] && i < last)
            {
                i++ ;
            }
            while ( k[j] > k[part])
            {
                j-- ;
            }
            if (i < j)
            {
                temp = k[i];
                k[i] = k[j];
                k[j] = temp;
                sum2+=1;
            }
        }


         sum2 += 1;
         temp = k[part];
         k[part] = k[j];
         k[j] = temp;
         QuickSort(k,first,j-1);
         QuickSort(k,j+1,last);




    }
    average = sum2 / n;
    return average;




}

[iMalc]

In lines 551 to 566 you seem to get mixed up between m and mid. Decide what each variable is for and work out which should be used when. That should fix your immediate concern. Now that I've helped you with that, I'd like you to do a few other things with that code for us both...

Can you please give your functions return types and put function prototypes for them up above main. Then turn your compiler warning levels up so that it can warn you about silly mistakes properly.

Your loops for generating random numbers such as line 47, have a buffer overflow, due to an off-by-one.

You also aren't checking the result of malloc, so if I enter one billion for n, then your app will probably just crash. Good programs don't just crash.

You should take those srand lines out and just call srand once at the top of your program.

What is the purpose of returning a value from the sorting algorithms? You aren't actually using it.

[Salem]

Re: compiler warning messages.

$ gcc -Wall -g foo.c
foo.c: In function ‘main’:
foo.c:46:18: warning: implicit declaration of function ‘srand’ [-Wimplicit-function-declaration]
foo.c:49:21: warning: implicit declaration of function ‘rand’ [-Wimplicit-function-declaration]
foo.c:60:18: warning: implicit declaration of function ‘SelectionSort’ [-Wimplicit-function-declaration]
foo.c:98:18: warning: implicit declaration of function ‘InsertionSort’ [-Wimplicit-function-declaration]
foo.c:132:18: warning: implicit declaration of function ‘BubbleSort’ [-Wimplicit-function-declaration]
foo.c:166:18: warning: implicit declaration of function ‘HeapSort’ [-Wimplicit-function-declaration]
foo.c:202:18: warning: implicit declaration of function ‘MergeSort’ [-Wimplicit-function-declaration]
foo.c:244:18: warning: implicit declaration of function ‘QuickSort’ [-Wimplicit-function-declaration]
foo.c: At top level:
foo.c:291:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c:326:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c: In function ‘InsertionSort’:
foo.c:328:9: warning: unused variable ‘sum1’ [-Wunused-variable]
foo.c: At top level:
foo.c:364:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c: In function ‘BubbleSort’:
foo.c:366:9: warning: unused variable ‘sum1’ [-Wunused-variable]
foo.c: At top level:
foo.c:403:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c: In function ‘HeapSort’:
foo.c:410:9: warning: implicit declaration of function ‘fixheap’ [-Wimplicit-function-declaration]
foo.c:405:9: warning: unused variable ‘sum1’ [-Wunused-variable]
foo.c: At top level:
foo.c:446:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c: In function ‘fixheap’:
foo.c:453:5: warning: implicit declaration of function ‘left’ [-Wimplicit-function-declaration]
foo.c:463:9: warning: implicit declaration of function ‘right’ [-Wimplicit-function-declaration]
foo.c:448:12: warning: unused variable ‘temp2’ [-Wunused-variable]
foo.c: At top level:
foo.c:518:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c: In function ‘MergeSort’:
foo.c:529:9: warning: implicit declaration of function ‘Merge’ [-Wimplicit-function-declaration]
foo.c: At top level:
foo.c:540:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c:598:1: warning: return type defaults to ‘int’ [-Wreturn-type]
foo.c: In function ‘Merge’:
foo.c:593:1: warning: control reaches end of non-void function [-Wreturn-type]
foo.c: In function ‘fixheap’:
foo.c:493:3: warning: control reaches end of non-void function [-Wreturn-type]

[anduril462]

Some other notes:

• Global variables are bad, read this link. Declare i, j, temp, position, n and average in the appropriate functions and pass them to other functions as needed.
• Your code for each switch statement in main is identical, except for two things, the sort function you call, and the name of the sort you use to print out the timing statistics. You should put the common code outside the switch, and only do the differing code inside the switch, it would be much cleaner. See below for an example. This would also help eliminate the following problem.
• You forget to free(A) in several places, which creates a memory leak if I run your program continuously. By moving common code outside the switch, you only have to worry about malloc'ing, error checking and freeing in one place. Again, example below.

Better switch statement in main function:

char *sort_name = "NONE";
...
printf("Parakalo oriste to megethos tou pinaka: \t");
scanf("%d", &n);
int *A = (int *) malloc(n * sizeof(int));
// check that malloc succeeded -- if not, exit your program with an error, you can't continue
srand(time(NULL));
for (i = 0; i <= n; i++) {
    A[i] = 1 + rand() % 10;
}


clock_t start, end;
double elapsed;
start = clock();
switch (choise) {
    case 1:
        SelectionSort(A, n);
        sort_name = "SELECTION";
        break;
    case 2:
        SelectionSort(A, n);
        sort_name = "SELECTION";
        break;
    ...
}
end = clock();
elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;


printf("\n\n Mesos xronos %s SORT :%f\n", sort_name, elapsed);
printf("\n Mesos #oros SELECTION SORT: \t %d", sort_name, average);
free(A);

See how much more concise that code is? And how many fewer lines of code you have to maintain and worry about?


Also, if exact timing statistics are super critical, you could move the start and end clock() calls into each case statement, immediately surrounding the sort call. This would only give minimal improvement to the accuracy of the timing statistics however.