Like Tree4Likes
  • 1 Post By rags_to_riches
  • 1 Post By anduril462
  • 1 Post By iMalc
  • 1 Post By laserlight

Runtime Hangup with Merge Sort of 2D array

This is a discussion on Runtime Hangup with Merge Sort of 2D array within the C Programming forums, part of the General Programming Boards category; I have never done a merge sort for a 2d array so I'm struggling a bit with it. Here is ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    4

    Runtime Hangup with Merge Sort of 2D array

    I have never done a merge sort for a 2d array so I'm struggling a bit with it. Here is my code:

    Code:
    /********************************************************************************
    FUNCTION NAME: mergeSort
    INPUTS:  roomsize (double array)
             roomprofit (double array)
             firstIndex (int) - first value for unsorted array index
             lastIndex (int) - last value for unsorted array index
             array (int) - specificies which array needs to be sorted
             column (int) - specifices which column needs to be sorted
             sortType (int) specifices which sort is needed
    OUTPUTS: Recursive call to mergeSort allows for the array to be divided in half
             with each call.
             Calls mergeLtoS if items need to be sorted from greatest to smallest
             Calls mergeStoL if items need to be sorted from smallest to largest
    RETURN:  None
    PURPOSE: Breaks up an unsorted array in preperation for sorting merge
    **********************************************************************************/
    int mergeSort (double roomprofit[25][5], int firstIndex, int lastIndex, int sortType, int array, int column)
    {
      if ( firstIndex < lastIndex)
        {
          mergeSort (roomprofit, firstIndex, (firstIndex+lastIndex)/2, sortType, array, column);
          mergeSort (roomprofit, (firstIndex+lastIndex)/2 +1, lastIndex, sortType, array, column);
    
    
          switch (sortType)
            {
            case 1:   mergeLtoS(roomprofit, firstIndex, (firstIndex+lastIndex)/2, (firstIndex+lastIndex)/2 + 1, lastIndex, array, column);
                      break;
    
    
            case 2:   mergeStoL(roomprofit, firstIndex, (firstIndex+lastIndex)/2, (firstIndex+lastIndex)/2 + 1, lastIndex, array, column);
                      break;
            }
        }
    }
    /********************************************************************************
    FUNCTION NAME: mergeLtoS
    INPUTS:  roomsize (double array)
             roomprofit (double array)
             firstIndex1 (int)
             lastIndex1 (int)
             firstIndex2 (int)
             lastIndex2 (int)
             array (int) - specifies which array needs to be sorted
             column (int) - specifices which column needs to be sorted
    OUTPUTS: calls mergeMove to merge compared array sections together
    RETURN:  None
    PURPOSE: Compares divided array sections in prep for merge to greatest to smallest
    **********************************************************************************/
    void mergeLtoS(double roomprofit[25][5], int firstIndex1, int lastIndex1, int firstIndex2, int lastIndex2, int array, int column)
    {
      double tempArray[25][5] = {{0}};
      int index, index1, index2;
      int num;
    
    
      index = 0;
      index1 = firstIndex1;
      index2 = firstIndex2;
      num = lastIndex1 - firstIndex1 + lastIndex2 - firstIndex2 + 2;
    
    
     if (array == 3)
        {
          while ( (index1 <= lastIndex1) && (index2 <= lastIndex2) )
            {
              if (roomprofit[index1][column] > roomprofit[index2][column])
                {
                  tempArray[index++][0] = roomprofit[index1++][0];
                  tempArray[index++][1] = roomprofit[index1++][1];
                  tempArray[index++][2] = roomprofit[index1++][2];
                  tempArray[index++][3] = roomprofit[index1++][3];
                  tempArray[index++][4] = roomprofit[index1++][4];
                }
              else
                {
                  roomprofit[index1++][0] = tempArray[index++][0];
                  roomprofit[index1++][1] = tempArray[index++][1];
                  roomprofit[index1++][2] = tempArray[index++][2];
                  roomprofit[index1++][3] = tempArray[index++][3];
                  roomprofit[index1++][4] = tempArray[index++][4];
                }
            }
          if (index1 > lastIndex1)
            {
              mergeMove(roomprofit, index2, lastIndex2, tempArray, index);
            }
           else
            {
              mergeMove(roomprofit, index1, lastIndex1, tempArray, index);
            }
          mergeMove (tempArray, 0, num-1, roomprofit, firstIndex1);
        }
    }
    
    
    /********************************************************************************
    FUNCTION NAME: mergeMove
    INPUTS:  arrayList1 (double array)
             arrayList2 (double array)
             firstIndex1 (int)
             firstIndex2 (int)
             lastIndex1 (int)
    OUTPUTS: RETURN:  None
    PURPOSE: Combines sections two lists of a sorted array.
    **********************************************************************************/
    void mergeMove(double arrayList1[25][5], int firstIndex1, int lastIndex1, double arrayList2[25][5], int firstIndex2)
    {
      while (firstIndex1 <= lastIndex1)
        {
          arrayList2[firstIndex2++][0] = arrayList1[lastIndex1++][0];
          arrayList2[firstIndex2++][1] = arrayList1[lastIndex1++][1];
          arrayList2[firstIndex2++][2] = arrayList1[lastIndex1++][2];
          arrayList2[firstIndex2++][3] = arrayList1[lastIndex1++][3];
          arrayList2[firstIndex2++][4] = arrayList1[lastIndex1++][4];
        }
    }
    /**** the function call and assignments for the merge sort from main ****/
     sortType = 1;
     array = 3;
     column = GROSS;
    
    
     roomprofitPrint(roomprofit, salesroom, roomname);
     mergeSort (roomprofit, 0, 25, sortType, array, column);
     roomprofitPrint(roomprofit, salesroom, roomname);
    

    This is my output when I run this portion of the program:

    -----------------------------------------------------------------
    Room Profit Information
    -----------------------------------------------------------------
    | Type | Gross Income | Net Profit |
    -----------------------------------------------------------------
    Sales 1 51187.50 21937.50
    Sales 2 25923.25 12230.75
    Hangup


    I am pretty sure the problem is the merge call instead of the prints. I have tested the roomprofitPrint function separately and it works every time its used unless the merge functions are called first. I'm just not sure where the error is, but I know I was guessing my way through how a 2D array would apply to the merge sort algorithm. Some advice on where my thinking is wrong would be greatly appreciated.

    Thanks

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Telling us what your output is, is only part of the equation. What was the input you gave it? What output should you be getting? Also, providing that main function, and anything else we need to test this program would be immensely helpful. I'll do a quick reading of your code anyway, but my results would be much better if you gave me a complete setup to test with.

    EDIT: Also, define how you want this 2-d array sorted. By what criteria are you sorting rows? Columns? Does the order in which you sort those matter, i.e. rows then columns vs. columns then rows?
    Last edited by anduril462; 10-27-2012 at 11:53 AM.

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    4
    I need the entire array to be sorted based on the values in a specific Column. The information in the rows is associated though so I can't just sort the column first and loose associated row data. The output which is printing seems right until it gets the Hangup. This is a massive project (4000 lines) so including all of the code is a challenge, I would have to post up at least 5 more functions to show you how the user input is being taken from the user to calculate roomprofit and then finally get sorted and printed not to mention my massive list of defined constants so you could made sense of it all. I will be more than happy to do that if it is needed but I am more than willing to test the code myself. What I am really looking for is some more information on how the merge sort applies to 2d arrays and were I might be thinking about it wrong. If you could give me a new direction to work with I will put the work into it.

  4. #4
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,648
    Salem likes this.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Code:
                  tempArray[index++][0] = roomprofit[index1++][0];
                  tempArray[index++][1] = roomprofit[index1++][1];
                  tempArray[index++][2] = roomprofit[index1++][2];
                  tempArray[index++][3] = roomprofit[index1++][3];
                  tempArray[index++][4] = roomprofit[index1++][4];
    You are incrementing index and index1 5 times. The code copies a diagonal portion of the 2D matrix to some other diagonal portion.
    You probably only want to increment those once, after all the copies are done.
    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"

  6. #6
    Registered User
    Join Date
    Oct 2012
    Posts
    4
    So I don't have to increment each row for each column with a 2D array? I have to put some value into the index for the columns though. I tried this:

    Code:
    arrayList2[firstIndex2++][firstIndex2++] = arrayList1[lastIndex1++][lastIndex1++];
    And I got the exact same output... only instead of a Hangup error I am getting a Segmentation Fault now.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Okay, here's a couple things to help you test:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    // slightly smaller array, making it easier to test
    #define MAX_R       10
    #define MAX_C       5
    
    /* your function mergeMove, mergeLtoS and mergeSort are here, in that order, to avoid "undefined function" warnings */
    
    
    void printArray(double array[MAX_R][MAX_C])
    {
        int r, c;
    
    
        for (r = 0; r < MAX_R; r++) {
            for (c = 0; c < MAX_C; c++) {
                printf("%7.1f", array[r][c]);
            }
            putchar('\n');
        }
    }
    
    
    
    
    int main(int argc, char **argv)
    {
        int r, c;
        int sortType = 1;
        int array = 3;
        int column = 0;
        double roomprofit[MAX_R][MAX_C];
    
    
        if (argc >= 2) {
            column = atoi(argv[1]);
            if (column >= MAX_C) {
                fprintf(stderr, "Column must be between 0 and %d inclusive\n", MAX_C - 1);
                return 1;
            }
        }
    
    
        srand(time(NULL));
        for (r = 0; r < MAX_R; r++) {
            for (c = 0; c < MAX_C; c++) {
                roomprofit[r][c] = rand() % 100;
            }
        }
    
    
        printArray(roomprofit);
        mergeSort(roomprofit, 0, MAX_R, sortType, array, column, 0);
        printArray(roomprofit);
    
    
        return 0;
    }
    I don't need 4k lines of code, just something like this would have been enough. Note, you should probably be testing the merge sort in isolation anyways, just to make sure you aren't encountering problems related to other code (e.g. calculating roomprofit values). I declared MAX_R and MAX_C as 10 and 5 respectively, to avoid magic numbers like 25 and 5, and to keep things a little smaller, so it's easier to verify by looking at the results.

    You simply compile your program, then run it as: program_name <column>, where <column> is a valid column number to sort on.

    Learning to use a debugger would be a great way to track down your seg faults. You run the code in the debugger, and when it seg faults, the debugger stops, and you can print a stack trace that tells you the line number of your code where the crash happened, and all the functions that were called, and their parameters, when the crash occurred. You can print the values of any variables and make sure everything looks good. If you ever plan on being a good programmer, you must learn to use a debugger.

    Tools like valgrind and electric fence are very useful for tracking down problems like this too. They're not too difficult to use, at least for basic stuff like this.

    In lieu of that, to get a quick solution, try adding debugging output to make sure you're calling things correctly, variables have the expected values, etc. For example, in mergeSort, ad the following line to the top of the function. Comment out the calls to mergeLtoS and mergeStoL for now, just make sure all the indexes are correct for all your recursive calls, and that your base case works.
    Code:
    fprintf(stderr, "mergeSort called with first and last indexes %d, %d\n", firstIndex, lastIndex);
    Once you verify that, uncomment the calls to mergeLtoS and mergeStoL. Add a similar debugging code to them, and comment out calls to mergeMove. Make sure you add debug output in all the critical places, for example at the top and bottom of the while loop, and after the while loop. I'm guessing, with all the index++ type of stuff, you go off the end of your array somewhere, and corrupt data.

    I have a feeling you did too much programming before you stopped to test anything. You should plan your solution carefully, then write no more than 5-10 lines at a time, stop, compile, fix all compilation error and warnings, and make sure those lines are working as expected. Move on to the next 5-10 lines. Repeat until done. Also, it may be beneficial to set aside your current mergeLtoS, mergeStoL and mergeMove functions for now, and start those from scratch, working in smaller chunks.
    rags_to_riches likes this.

  8. #8
    Registered User
    Join Date
    Oct 2012
    Posts
    4
    I can't thank you enough for your very informative reply. I have tracked down the problem, somehow my index values getting incremented up to 200 or so instead of staying within the range and that is making a complete mess of things especially in the mergeMove function given the way I have set it up.

    Considering I have all the control structures that the example code for 1d arrays I expected the problem was somewhere in my handling of the 2d array. Yay at least I got something right. I do test my program as I build it, however this particular program is my first really massive project that has been building on itself for the entire year. I haven't done a very good job of working out how to remove old parts and make a test environment for the new stuff I am building so I can do more isolated testing and you are absolutely right that it has hindered me.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Glad you got it sorted out. And don't worry, you'll develop these skills with time. It's just too bad that so many schools/professors don't really teach them in conjunction with the rest of the course material. They're immensely helpful, not only for school, but in the programming industry, and even in other industries. You'll just have to practice them on your own.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by orlileithian View Post
    So I don't have to increment each row for each column with a 2D array? I have to put some value into the index for the columns though. I tried this:

    Code:
    arrayList2[firstIndex2++][firstIndex2++] = arrayList1[lastIndex1++][lastIndex1++];
    And I got the exact same output... only instead of a Hangup error I am getting a Segmentation Fault now.
    You tried something totally random without paying attention to what I said. You were incrementing the variables 5 times, I said you should only do it once, and then you change it to 10 times instead?! Actually I think what you changed it to is probably undefined behaviour.
    What you were meant to realise is that you can't have those ++ inside the expression where the array values are copied over. Only do that once after the 5 items are copied over.
    Salem likes this.
    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"

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by iMalc
    Actually I think what you changed it to is probably undefined behaviour.
    It was undefined behaviour to begin with.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by laserlight View Post
    It was undefined behaviour to begin with.
    Only if it was of the end off the array or something, otherwise the lines he had previously are themselves not UB e.g.:
    Code:
    tempArray[index++][0] = roomprofit[index1++][0];
    that is not the same variable being incremented in both places there. No UB there.
    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"

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Oh right. index versus index1. Bad naming.
    iMalc likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort (Array)
    By Jack Hammer in forum C++ Programming
    Replies: 3
    Last Post: 03-05-2011, 01:37 PM
  2. Merge sort fails to sort
    By Cresh07 in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2009, 11:17 AM
  3. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 05:48 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21