Thread: 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

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.

See also here

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.

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.

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.

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.