Thread: Merge sort please

  1. #1
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683

    Merge sort please

    I have created a merge sort program... which will take all the numbers to sort from the command line.. The code is below.. please check it and comment.. how can the code be optimized, made better etc etc..


    Code:
    # include <stdio.h>
    # include <stdlib.h>
    
    int main(int argc,char *argv[])
    {
    int *array,i;
    if(argc<3)
    	{
    	printf("\nInsufficient arguments provided\n");
    	return(1);
    	}
    
    if((array=(int*)calloc(argc-1,sizeof(int)))==NULL)
    	{
    	printf("Error allocating memory");
    	exit(1);
    	}
    
    for(i=1;i<argc;i++)
    	{
    	
    	if(isalpha(*argv[i]))
    	{
    	printf("\nInvalid argument encountered\n");
    	free(array);
    	exit(1);
    	}
    	else
    	array[i-1]=atoi(argv[i]);
    		
    	}
    	       	
    msort(array,0,argc-2);
    
    for(i=0;i<argc-1;i++)
    printf("\n%d",array[i]);
    
    free(array);
    return 0;
    }
    
    
    msort(int *array,int lower,int upper)
    {
    int temp,*arr,i,down,up,tempup;
    if(upper-lower==1)
    	{
    	
    	if(array[lower]>array[upper])
    		{
    		temp=array[upper];
    		array[upper]=array[lower];
    		array[lower]=temp;
    		}
    	
    	}
    else if(upper-lower>1)
    	{
    	msort(array,lower,(lower+upper)/2);
    	msort(array,((lower+upper)/2)+1,upper);
    	}
    
    		if((arr=(int*)calloc(upper-lower+1,sizeof(int)))==NULL)
    		{
    		printf("Error allocating memory");
    		return(1);
    		}
    	
    	if((upper-lower+1)>2)
    	{
    	for(i=0;i<(upper-lower)+1;i++)
    	arr[i]=array[lower+i];
    	
    	down=0;
    	
    	if((upper-lower+1)%2!=0)
    		up=((upper-lower+1)/2)+1;
    	else
    		up=((upper-lower+1)/2);
    	
    	tempup=up;
    	
    		for(i=0;i<upper-lower+1;i++)
    	{
    	
    		if(down==tempup)
    		{
    		array[lower+i]=arr[up];
    		up++;	
    		continue;
    		}
    		
    	
    		if(up>=(upper-lower+1))
    		{
    		array[lower+i]=arr[down];
    		down++;
    		continue;
    		}
    	
    		if(arr[up]>arr[down])
    		{
    		array[lower+i]=arr[down];
    		down++;	
    		continue;
    		}
    		
    	
    		if(arr[up]<arr[down])
    		{
    		array[lower+i]=arr[up];
    		up++;
    		continue;
    		}
    	
    		if(arr[up]==arr[down])
    		{
    		array[lower+i]=arr[up];
    		up++;
    		continue;
    		}
    		
    		
    	}
    	
    		free(arr);
    	}
    
    }
    thanks in advance
    bye
    Vasanth

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Fix the indentation would be a start

    > return(1);
    Is ignored by outer levels of your recursive calls, and ignored as the overall result.

    You cast the result of calloc - see the FAQ

    It's hard to tell from your sort code, but I think there may be a memory leak.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    Hi Again,
    I have modified my code.. can you please review the code and comment.. This one has both merge sort and insertion sort as options


    Code:
    
    
    # include <stdio.h>
    # include <stdlib.h>
    # include <ctype.h>
    
    void msort (int *, int, int);	/*Function prototypes for Merge sort and Insertion sort functions */
    void insertion (int *a, int n);
    
    int
    main (int argc, char *argv[])
    {
      int *array, i;		/*array to hold the digits passed from the command line */
      char ch = ' ';
      if (argc < 3)			/* If one or less than one argument is provided, there is no need of sorting */
        {
          printf ("\nInsufficient arguments provided\n");
          return (1);
        }
    
      if ((array =  calloc (argc - 1, sizeof (int))) == NULL)	/*Memmory is dynamically allocated to hold the arguments passed through command line */
        {
          printf ("Error allocating memory");	/*Any error is allocation of memory will result in an error message and the program exits */
          exit (1);
        }
    
      for (i = 1; i < argc; i++)	/*The given input is checked for validity by checking wheather its a number */
        {				/*If a valid number is found it is copied into the array */
    
          if (isalpha (**(argv + i)))
    	{
    	  printf ("\nInvalid argument encountered\n");
    	  free (array);
    	  exit (1);
    	}
          else
    	{
    	  *(array + i - 1) = atoi (*(argv + i));
    	}
        }
    
      /*The user is given the choice of using insertion or merge sort to sort the array */
    
      printf ("\n Press 'i' for insertion sort or 'm' for merge sort > ");
      while (ch != 'i' && ch != 'm')	/*Input is expected untill a valid input is gievn */
        ch = getchar ();
    
      /*Respective sorting functions are called based on the user input */
    
      (ch == 'm') ? (msort (array, 0, argc - 2)) : (insertion (array, argc - 1));
    
      /*The sorted array is displayed on the screen */
    
      for (i = 0; i < argc - 1; i++)
        printf ("\n%d", *(array + i));
    
      /*The allocated memory for the array is deallocated/freed */
    
      free (array);
      printf ("\n");		/*Displays prompt in the next line */
      return 0;
    }
    
    
    
    void
    insertion (int a[], int n)	/*The insertion sort function accepts the array pointer and the number of elements as argument */
    {
      int i, temphold, num;		/*Variables : i as counter, temphold used to swap, num to get value of i into while loop */
      for (i = 1; i < n; i++)	/*Loop will run till the last element is sorted */
        {
          num = i;
          /*
             The while loop is run until the elements in the left section below element i are ordered     
           */
          while (*(a + num) < *(a + num - 1))
    	{
    	  temphold = *(a + num);
    	  *(a + num) = *(a + num - 1);
    	  *(a + num - 1) = temphold;	/* The numbers are swapped */
    	  if (num - 1 == 0)	/*The loop is broken when num reaches start of left section */
    	    break;
    	  else
    	    num--;		/* Num is moved left to compare with the previous element */
    	}
        }
    
    
      return;
    }
    
    
    void
    msort (int array[], int lower, int upper)	/* The merge sort recursive function accepts the array pointer, lower and upper bound as arguments */
    {
    
      int temp, *arr, i, down = 0, up, tempup;
    /*
    The below if block runs when the array is split into very small part 
    and where only 2 elemets exist. So these 2 elemts are compared and sorted is proper order
    */
      if (upper - lower == 1)
        {
    
          if (*(array + lower) > *(array + upper))
    	{
    	  temp = *(array + upper);
    	  *(array + upper) = *(array + lower);
    	  *(array + lower) = temp;
    	}
    
        }
    
    /*
    The below block is run if the array has more than 2 elements
    Then the array is again split into 2 parts by calling the same function with different lower and upper bound
    */
    
      else if (upper - lower > 1)
        {
          msort (array, lower, (lower + upper) / 2);
          msort (array, ((lower + upper) / 2) + 1, upper);
        }
    
    
    /*
    The split arrays have to be merged (at least logically). This part happens in the below bloack
    A temp array is created to hold the elements so that the 2 arrays can be merged (sorted)
    */
      if ((arr =  calloc (upper - lower + 1, sizeof (int))) == NULL)
        {
          printf ("Error allocating memory");
          return;
        }
    
      if ((upper - lower + 1) > 2)
        {
          for (i = 0; i < (upper - lower) + 1; i++)	/*The elements are copied into the temp array arr */
    	*(arr + i) = *(array + lower + i);
    /*
    The upper bound is calculated differently when there are odd or even number of elements
    in the array
    */
          ((upper - lower + 1) % 2) != 0 ? (up =
    					((upper - lower + 1) / 2) + 1) : (up =
    									  ((upper - lower + 1) / 2));
          tempup = up;		/*The upper bound is copied into another variable as this value is required later for some calculation */
          for (i = 0; i < upper - lower + 1; i++)	/*Upper-lower+1 gives the number of elements in the given section of the array */
    	{
    
    	  if (down == tempup)	/*When the lower bound of the temp array reaches the upper bound it means that the left part
    				   or the section of the array is empty and there is no need to compare */
    	    {
    	      *(array + lower + i) = *(arr + up);
    	      up++;
    	    }
    
    	  else if (up >= (upper - lower + 1))	/*When the upper bound of the temp array reaches the end of the array section it means that the right part
    						   or the section of the array is empty and there is no need to compare */
    	    {
    	      *(array + lower + i) = *(arr + down);
    	      down++;
    	    }
    
    	  else
    	    /*
    	       When the left and right part of the array contains elements the first elements in both the array are compared and
    	       the smallest of the two is owerwritten to the main array location starting from lower bound. 
    
    	       The first elements of the left section of temp array only need to be compared with 
    	       with its right counterpart as both of them are already individually sorted
    	     */
    	    (*(arr + up) > *(arr + down)) ? (*(array + lower + i) =
    					     *(arr + down),
    					     down++) : (*(array + lower + i) =
    							*(arr + up), up++);
    	}
          free (arr);		/*The memory allocations are freed */
        }
    
      return;
    }
    thanx in advance
    bye
    Last edited by vasanth; 11-09-2003 at 12:11 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort the best sorting algorithm?
    By sehr alt in forum A Brief History of Cprogramming.com
    Replies: 21
    Last Post: 06-20-2007, 02:19 PM
  2. Merge Sort Help
    By blindman858 in forum C++ Programming
    Replies: 5
    Last Post: 05-14-2005, 09:47 PM
  3. Merge Sort
    By blindman858 in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2005, 11:14 AM
  4. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  5. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM