Merging k sorted arrays - problem with memory

Question

The objective is to sort a i x j matrix of words in a 1D matrix of words in alphabetical order(every row in the original matrix is already sorted). The matrix is read from a file and stored in a three star pointer ***index, it is dynamically allocated like this (in a separate function):

char ***index;
index= (char ***) malloc(*row * sizeof(char **));
...
for (int i = 0; i < *row; ++i){

    index[i]= (char **) malloc(*col * sizeof(char **));
    for (int j=0; j<*col; j++) {

        fscanf(fp,"%s",tmp);
        index[i][j]=strdup(tmp);
    }

}

I then pass the index to my sorting function: char **sort_data(char ***index, int row,int col).

It is nothing special just a merge sort algorithm that:

1. checks the first elements of each row of ***index
2. moves the "smallest" word to **sortedIndex

3. substitutes the sorted word with a new one from the same row.

   char **sort_data(char ***index, int row,int col){
   
   int i,posInIndex,smallestCharPos,*tracker;
   char **sortedindex,*buffer;
   sortedindex=(char **) malloc((row*col)*sizeof(char*));
   tracker= (int*) calloc(row, sizeof(int));
   
   posInIndex=0;
   while (posInIndex<row*col) {
       smallestCharPos=-1;
       for (i=0; i<row; i++) {
           if ((smallestCharPos==-1)||(strcmp(index[i][tracker[i]], buffer)<0)) {
               smallestCharPos=i;
               buffer=index[i][tracker[i]];
           }
   
       }
       sortedindex[posInIndex]=index[smallestCharPos][tracker[smallestCharPos]];
       posInIndex++;
       tracker[smallestCharPos]++;
   }
   free(tracker);
   return (sortedindex);
   
   }
   

After some iterations(depends on matrix size) of the for loop, I get a EXC_BAD_ACCESS (code=1, address=0x14000001f5) at the if statement which leads me to believe it's an issue with my memory allocation but i cannot spot the mistake.

An example of a matrix to sort would be (this particular matrix gives me trouble after 10 iterations of the for loop):

milano torino venezia

bari genova taranto

firenze napoli roma

bologna cagliari palermo

Answer 1

The problem is that you don't track when you are done with a row. Even if you have already used all words of a row, you just continue looking at the row as if there are more words to handle.

You need to add some code to skip the rows that are fully handled already.

Try changing this:

if ((smallestCharPos==-1)||(strcmp(index[i][tracker[i]], buffer)<0)) {
     ...
}

to

if (tracker[i] < col)
{
     if ((smallestCharPos==-1)||(strcmp(index[i][tracker[i]], buffer)<0)) {
         ...
     }
}