Thread: my mergeSort

  1. #1
    Registered User
    Join Date
    Jan 2010
    Posts
    103

    my mergeSort

    Hey, I am trying to make a mergeSort to sort an array of

    Code:
    struct student {
       char first[30];
       char last[30];
       int month;
       int day;
       int year; //this is not looked at while sorting
    }
    This is my function(s):

    Code:
    //sorts left and right halves and then merges them together; recursively called
    //to get smaller halves
    void mergeSort(struct student* list[], int low, int high) {
       if(low<high) {
          int mid=(low+high)/2;
          printf("\nMerge LOW,MID,HIGH: %d-%d-%d\n",low,mid,high);
          mergeSort(list,low,mid);
          mergeSort(list,mid+1,high);          
          merge(list,low,mid+1,high);
       }  
    }
    
    //takes a second array and organizes each half of the array alphabetically, and then
    //replaces the values in the array
    void merge(struct student* list[], int low, int mid, int high) {
       int length=high-low+1;
       printf("\nLength: %d\n",length);
       struct student* temp[1002];
       int count1=low, count2=mid;
       int index=0;
       while((count1<mid) && (count2<high)) {
          if(compareAge(list[count1],list[count2])==-1) {
             temp[index]=list[count1];
             index++;
             count1++;                                    
          }
          else {
             temp[index]=list[count2];
             index++;
             count2++;  
          }
       }
       int i;
       if(count1<mid) {
          for(i=index;i<length;i++) {
          temp[i]=list[count1];
          count1++;                       
          }                
       }
       else if(count2<high) {
          for(i=index;i<length;i++) {
          temp[i]=list[count2];
          count2++;                       
          }  
       }
       for(i=0;i<high;i++) {
          if(temp[i]->first=="NULL" || temp[i]->last=="NULL") {
             printf("Temp[%d]: NULL",i);            
          }
          else 
             printf("Temp[%d]: %s %s\n",i,temp[i]->first,temp[i]->last);      
       }
       for(i=low;i<=high;i++) {
          list[i]=temp[i-low];
       }
       for(i=0;i<high;i++) {
          if(list[i]->first=="NULL" || list[i]->last=="NULL") {
             printf("List[%d]: NULL",i);            
          }
          else 
             printf("List[%d]: %s %s\n",i,list[i]->first,list[i]->last);                   
       }
    }
    Some helpful advice please The error produced is that it crashes randomly in the middle of printing. What's worse, based on previous output before it prints the whole and finished. However, if I take out the prints, then it finishes and the program does NOT crash. However, it prints them out of order. Anybody can see what's wrong with my mergeSort?

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Soulzityr View Post
    The error produced is that it crashes randomly in the middle of printing.
    You just need to run it once thru a debugger and find the cause of the crash. Please tell us what platform you are using so someone can explain how to use a debugger here, it is not hard.

    One observation:
    Code:
    void mergeSort(struct student* list[], int low, int high) {
       if(low<high) {
          int mid=(low+high)/2;
          printf("\nMerge LOW,MID,HIGH: %d-%d-%d\n",low,mid,high);
          mergeSort(list,low,mid);
          mergeSort(list,mid+1,high);          
          merge(list,low,mid+1,high);
       }  
    }
    The red line is problematic. It occurs first. Given the list:
    2 3 4 5 6 7 8
    We now go: "2 3 4 5" then "2 3" then "2 2" then "2 2" then "2 2" then "2 2" ad infinitum.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    really? cuz i copied the formula straight from my instructor's website; it was offered to us since we had to do a lot more with the program. but hmm i see the problem. but isn't that covered with the if(low<high) part? that makes it so it wont happen, right?

    btw i use dev-cpp

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Soulzityr View Post
    really? cuz i copied the formula straight from my instructor's website; it was offered to us since we had to do a lot more with the program. but hmm i see the problem. but isn't that covered with the if(low<high) part? that makes it so it wont happen, right?
    Yeah okay yer right. It will bounce a back and complete the recursion from the last two elements. So the problem is in the other function.

    btw i use dev-cpp
    Windows or linux?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    hmm which function, you mean the merge? yes...but i cant seem to find the problem. as far as i can tell, it should be working just fine...what more information do i need to show here to help address the issue? the output, etc?

    and i use windows 7

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    No, you need to run it thru a debugger. The idea is, you compile the code with some symbols included (by the compiler -- you don't have to add change anything) in the executable so that the debugger can run the executable and identify the instruction during which "the crash" occurred. That instruction may be a line from your code, or (often enough) something within the standard (or other) library due to some kind of mis-use. In that case you can do a "backtrace" and in the end, find the exact line of code which resulted in "the crash".

    This is almost always a major clue about what went wrong. Me scrutinizing code that I haven't run/can't isn't always effective (as we just saw), and this kind of extrapolates into a problem whereby the person who wrote the code cannot see the error either, even when they can run it. Which that happens to everyone and that is why there are debuggers and also why, sooner or later, you will be learning to use one.

    Unfortunately, I don't program on windows or use dev-cpp so I can't help you with that part.
    Last edited by MK27; 03-24-2010 at 06:12 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is a recursive mergesort that you might compare with the program you have:

    It appears to work, but has not been thoroughly tested:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 200
    
    void merge(int A[], int Index[], int l, int m, int r);
    void mergesort(int *A, int *Index, int l, int r);
    void printIt(int *A);
    
    
    int main() {
      
      int i;
      int *A, *Index; 
    
      A = malloc(MAX * sizeof(int));
      Index = malloc(MAX * sizeof(int));
    
      if(!A || !Index) {
        printf("memory allocation failed - terminating program");
        return 1;
      } 
      for(i = 0; i < MAX; i++) {
        A[i] = rand() % 1000;
        Index[i] = 0;
      }
    
      printf("\n\n  Unsorted Data\n");  
      printIt(A);
      getchar();
    
      mergesort(A, Index, 0, MAX-1);
      printf("\n\n Sorted Data\n");
      printIt(A);
    
      free(A);
      free(Index);
      printf("\n\n\t\t\t     press enter when ready");
      i = getchar();
      return 0;
    }
    void mergesort(int *A, int *Index, int l, int r) {
       int m;
       if (l < r) {
          m = (l + r) /2;
          mergesort(A, Index, l, m);
          mergesort(A, Index, m + 1, r);
          merge(A, Index, l, m, r);
       }
    }
    
    /* 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 ends when lo = hi, i.e. when a sub-sequence 
    consists of only one element.
    */
    
    void merge(int A[], int Index[], int l, int m, int r)
    {
        int i, j, k;
    
        /* copy A to temp array Index */
        for (i = l; i <= r; i++)
            Index[i] = A[i];
    
        i = l; j = m + 1; k = l;
        /* copy back to A */
        while (i <= m && j <= r)
            if (Index[i] <= Index[j])
               A[k++] = Index[i++];
            else
               A[k++] = Index[j++];
    
        /* copy back remaining elements of first half (if any)  */
        while (i <= m)
            A[k++] = Index[i++]; 
    }
    /*Merge() does most of the work in Mergesort. The two halves are first copied 
    into an extra array, Index. Then 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();
    */
    void printIt(int A[]) {
      int i;
      for(i = 0; i < MAX; i++)
        printf(" %3d ", A[i]);
    
    }
    The output is good to see both the sorted, and unsorted int's, on the same page, if you keep the number of elements below 250 or so.

  8. #8
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    hmm the mergesort technique you have looks exactly the same as mine o_O is there any difference? because its not sorting correctly...

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Do you expect this:
    Code:
    if(temp[i]->first=="NULL" || temp[i]->last=="NULL") {
    to do anything useful? (Hint: == does not compare strings.)

    I'm also even wondering why that's there. Do you try to sort more items than there are?

  10. #10
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    oh no sorry i was doing that earlier to try and debug, cuz it was crashing so i figured it was trying to print NULL stuff

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    These are wrong:
    Code:
       if(count1<mid) {
          for(i=index;i<length;i++) {
          temp[i]=list[count1];
          count1++;                       
          }                
       }
       else if(count2<high) {
          for(i=index;i<length;i++) {
          temp[i]=list[count2];
          count2++;                       
          }  
       }
    You want to copy items until i is equal to mid in the first case, and i is equal to high in the second case. The variable 'length' should be removed.

    You may also have some off by one errors, depending on how you call 'mergesort'.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    when i changed from length to mid/high the program now crashes, so what does that mean? I think you're right that length there is wrong but now it crashes pretty early in trying to sort them.

    what is an "off by one" error?

    btw i dont know how im using the debugger. lol...ive been trying to use it but i guess i dont understand what it's telling me.

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Soulzityr View Post
    what is an "off by one" error?
    Aka, the fencepost error:

    Off-by-one error - Wikipedia, the free encyclopedia

    Easy to make, but usually also easy to identify and fix.

    btw i dont know how im using the debugger. lol...ive been trying to use it but i guess i dont understand what it's telling me.
    A little googling implies to me that dev-cpp used gdb on windows via a GUI. I can't help you with the gui, but try "gdb" at the command line to see if it exists. If it does I can explain how to find the seg fault here, and once you've seen gdb running on the command line probably the GUI will start to make more sense.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Soulzityr View Post
    when i changed from length to mid/high the program now crashes, so what does that mean? I think you're right that length there is wrong but now it crashes pretty early in trying to sort them.
    That shouldn't happen. Can you show us what the change looks like please?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    you mean as in the output? or in the code?

    Code:
       if(count1<mid) {
          for(i=index;count1<mid;i++) { //for(i=index;i<length;i++) doesnt crash
          temp[i]=list[count1];
          count1++;                       
          }                
       }
       else if(count2<high) {
          for(i=index;count2<high;i++) { //for(i=index;i<length;i++) doesnt crash
          temp[i]=list[count2];
          count2++;                       
          }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Mergesort in C
    By Oduig in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 11:30 AM
  2. How do I do MergeSort versus QuickSort instead?
    By dxfist in forum C++ Programming
    Replies: 9
    Last Post: 03-06-2008, 12:12 PM
  3. Natural Mergesort
    By wuzzo87 in forum C Programming
    Replies: 31
    Last Post: 04-14-2007, 09:41 PM
  4. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  5. Linked Lists + MergeSort....(how?)
    By JoshR in forum C++ Programming
    Replies: 4
    Last Post: 06-03-2005, 02:40 PM