Thread: Sorting function will not sort a .dat file of 100,000 integers

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    25

    Sorting function will not sort a .dat file of 100,000 integers

    My program will sort a .dat file with 2,000 integers just fine, and write it to a text file just fine as well. It will also sort 10,000 integers with no problem whatsoever. But when I try to sort a .dat file of 100,000 integers or 1,000,000 integers, my program freezes.

    Here is the source code, well commented I hope - let me know if I can clarify anything:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define SIZE 11
    int* mergeSort(int*, int); 
    int* merge(int*, int, int*, int);
    int main(void)
    {
    int* mergeSorted;
    int size;
    int indexCounter = 0;
    
    FILE *theFile;
    int i,j, count;
    
    
    //A.dat = 2,000 random integers
    //B.dat = 10,000 random integers
    //C.dat = 100,000 random integers
    //D.dat = 1,000,000 random integers
    //E through H.dat are in the same sequence, except they are nearly ordered rather
    //than random.
    
    
    
    
    //This is one specific instance of the CPU timing.
    //It also writes the numbers to a text file.
    
    //Reads the data file integers into a dynamic array
    theFile = fopen("F.dat", "rb");
         fread( &size, sizeof(int), 1, theFile);
         int* theArray = (int*) malloc((size)*sizeof(int));
         for(i=0;i<size;i++)
         fread( &(theArray[i]), sizeof(int), 1, theFile);    
         fclose(theFile);     
                        unsigned long finish = 0L, start = 0L;
    //clocking the merge sort function     
                             start = clock();
    
              mergeSorted = mergeSort(theArray,size);
                             finish = clock() - start;
                   finish = finish / (CLOCKS_PER_SEC / 1000);
                   
    //writing the sorted array to a text file
              FILE *aText;
              aText = fopen("fText.txt","w");
              fprintf(aText,"10000 random integers sorted:\n");
              for(i=0;i<1000;i++)
              {
              fprintf(aText,"\nRow %6d:    ",indexCounter);
                   for(j=0;j<10;j++)
                   {
                   fprintf(aText,"%6d ",mergeSorted[indexCounter]);
                   indexCounter++;
                   }
              }
              
    //Lastly print the sorting CPU time elapsed to the screen
    printf("Time to sort F.dat: %lu milliseconds\n", finish); 
    
    //If needed
    //system("Pause");
    return 0;
    }
    
    
    //Function Calls
    
    //Merge Sort function
    int* mergeSort(int* theArray,int size)
    {
         int i;
         //If the partition size is 1, we're done subdividing so return recursively
         if (size<=1)
         {
    ////////////////     printf("partition is now size 1, returning\n");
         return theArray;
         }
         else
         {
             int* left;
             int* right;
             int middle;
             int leftSize;
             int rightSize;
             int counter;
             middle = (size / 2) + 1;
    ////////////////         printf("Size:%d\n",size);
    ////////////////         printf("middle size: %d\n",middle);
    //dynamically allocating space for the left half of the partition
             left = (int*) malloc((middle-1)*sizeof(int));
             leftSize=(middle-1);
    ////////////////         printf("Left Size:%d\n",leftSize);
    //If size of subArray is odd, we have to make some adjustments
    //in how we handle the right half of the partition
             if(size%2==1)
             {
    //dynamically allocating the space for the right half of the partition
             right = (int*) malloc((middle)*sizeof(int));
             rightSize=middle;
             }
    //Else if size of subArray is even, proceed this way
             else
             {         
             right = (int*) malloc((middle-1)*sizeof(int));
             rightSize=(middle-1);
             }
    /////////////////         printf("Right Size:%d\n",rightSize);
    //Copying the left half of the partition to the array left[]
             for(i=0;i<(middle-1);i++)
             {
             left[i] = theArray[i];
    /////////////////         printf("left%d\n",left[i]);
             }
    //again we have to handle odd right half slightly different
             if(size%2==1)
             {
             counter=0;
    //Copying the right half of the partition to the array right[]
             for(i=(middle-1);i<size;i++)
             {
             right[counter] = theArray[i];
    /////////////////         printf("right%d\n",right[counter]);         
             counter++;
             }
             }
             else
             {
             counter = 0;
             for(i=(middle-1);i<size;i++)
             {
    
             right[counter] = theArray[i];
    /////////////////         printf("right%d\n",right[counter]);         
             counter++;
             }
             }
    
    /////////////////         system("Pause");
    //split the left side up until it is in size 1 subarrays
             left = mergeSort(left,leftSize);
    //split the right side up until it is in size 1 subarrays
             right = mergeSort(right,rightSize);
             int* merged;
    //merge left and right recursively
             merged = merge(left, leftSize, right, rightSize);
             return merged;
         }
    }
    
    
    //Merge Function
    int*  merge(int* left, int leftSize, int* right, int rightSize)
    {
          int leftSizeCopy,rightSizeCopy;
    /////////////////      printf("Merge function called. Left Size: %d, Right Size: %d\n",leftSize,rightSize);
          leftSizeCopy = leftSize;
          rightSizeCopy = rightSize;
          int counter = 0;
          int i;
          int* result = (int*) malloc ((leftSize+rightSize)*sizeof(int));
    //while there are unsorted numbers left
          while ( (leftSize > 0) || (rightSize > 0) )
          {
    
                
                int* holder;
    //if both sides have unsorted numbers in them
                if( (leftSize > 0) && (rightSize > 0) )
                {
    //compare the first cell on the left with first on the right
    //if it's less
                    if(left[0]<=right[0])
                    {
    //copy the number into a sorted array 
    //and copy all of the left side minus the copied number into a new malloc
    //then point left at the new malloc pointer                                    
                    result[counter] = left[0];
                    counter++;
                    leftSize--;
                    if(leftSize!=0)
                    {
                    holder = (int*) malloc((leftSize)*sizeof(int));
                    for(i=1;i<=leftSize;i++)
                    {
                    holder[i-1] = left[i];
                    }
                    left = holder;
                    }
                    }
    //else, if the right side's first cell is greater than that of the left side
                    else if(right[0]<left[0])
                    {
    //copy the number into the sorted array
    //and copy all of the right side minus the copied number into a new malloc
    //then point right at the new malloc pointer                                    
    
                        result[counter] = right[0];
                        counter++;
                        rightSize--;
                        if(rightSize!=0)
                        {
                        holder = (int*) malloc((rightSize)*sizeof(int));
                        for(i=1;i<=rightSize;i++)
                        {
                        holder[i-1] = right[i];
                        }
                        right = holder;
                        }
                    }
                }
                    else if(leftSize > 0)
    //if the left size is greater than 0 but the right side is emptied out
    //copy the cells over to the sorted array
    //and reduce the size of left as before using malloc
                    {
                    result[counter] = left[0];
                    counter++;
                    leftSize--;
                    if(leftSize!=0)
                    {
                    holder = (int*) malloc((leftSize)*sizeof(int));
                    for(i=1;i<=leftSize;i++)
                    {
                    holder[i-1] = left[i];
                    }
                    left = holder;
                    }
                    }
                    else if(rightSize > 0)
                    {
    //if the right size is greater than 0 but the left side is emptied out
    //copy the cells over to the sorted array
    //and reduce the size of right as before using malloc
                        result[counter] = right[0];
                        counter++;
                        rightSize--;
                        if(rightSize!=0)
                        {
                        holder = (int*) malloc((rightSize)*sizeof(int));
                        for(i=1;i<=rightSize;i++)
                        {
                        holder[i-1] = right[i];
                        }
                        right = holder;
                        }
                    }                                     
          }
          return result;        
    }
    Last edited by Derek Lake; 03-11-2012 at 03:09 AM. Reason: there was a printf typo which could have been confusing

  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
    I would look at how many malloc calls you have (there are NO free calls by the way, so it's one huge memory leak).

    I suggest more reading on how mergesort works, because it doesn't rely on you making 2^n COPIES of the array before you begin.
    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
    Registered User
    Join Date
    Sep 2011
    Posts
    25

    Memory leak and making 2^n copies

    Hey, thanks for your swift reply again Salem - you helped me before as well!

    Okay, I haven't put the free function in yet , but that is coming, I realize it doesn't have it.

    About making 2^n copies, where am I doing this? I have looked before the function call in main, and can't see what you're referring to.

    Oh and again, just to stress, my sort is working for 2,000 and 10,000 integers, just in case I hadn't made that clear.

    Hmm.. I've been looking over my code, are you referring to me using malloc to make a left array and a right array? I'm not sure how else to pass the left half and the right half recursively otherwise..
    Last edited by Derek Lake; 03-11-2012 at 03:32 AM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    mergesort calls mergesort - AFTER making a complete copy of the array (using malloc'ed memory)

    These recursive calls also make copies as well.

    In fact. they go on making copies until you've whittled down 1M to 1 (by repeatedly dividing by two).

    Replace your malloc calls with calls to myMalloc, as defined
    Code:
    void *myMalloc ( size_t size ) {
      static size_t total = 0;
      static int numCalls = 0;
      total += size;
      numCalls++;
      printf("%d calls, allocated %lu total bytes\n", numCalls, total );
      return malloc( size );
    }
    See how big numCalls and total grow with each size increment in your array.
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting integers and characters in C
    By kev2310 in forum C Programming
    Replies: 3
    Last Post: 02-07-2011, 09:16 AM
  2. Sorting an array of integers
    By supermeew in forum C Programming
    Replies: 4
    Last Post: 05-02-2006, 04:58 AM
  3. Replies: 9
    Last Post: 03-17-2006, 12:44 PM
  4. Sorting integers
    By Munkey01 in forum C++ Programming
    Replies: 3
    Last Post: 02-20-2003, 07:36 AM
  5. Sorting Integers
    By Beginnerinc in forum C Programming
    Replies: 7
    Last Post: 02-05-2003, 04:28 PM