0

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

Lundin
  • 195,001
  • 40
  • 254
  • 396
NotTheNSA
  • 3
  • 3
  • 1
    I see the allocation for e.g. `index[i]`, but not for `index[i][j]`? Is there any? Please read about [how to ask good questions](http://stackoverflow.com/help/how-to-ask), as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). And of course please learn how to create a [Minimal, Complete, and Verifiable Example](http://stackoverflow.com/help/mcve). Also, in C you [should not cast the result of `malloc` (and family)](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). – Some programmer dude Nov 09 '18 at 10:02
  • You'll probably want to post a full (minimal) program we can test; read the page on [MCVE](https://stackoverflow.com/help/mcve) for further guidance. In fact, you should probably test it yourself with a tool like `valgrind` that will point you to any invalid memory accesses in your code. – aaaaaa123456789 Nov 09 '18 at 10:03
  • 2
    I *think* buffer is uninitialised at the first iteration. Also: *three star programmer* – joop Nov 09 '18 at 10:04
  • 2
    @joop As `(smallestCharPos==-1)` is true at the first iteration the `strcmp` will not be executed. In other words - it doesn't matter that `buffer` is uninitialized at that point. That said - I wouldn't write such code as it is pretty confusing – Support Ukraine Nov 09 '18 at 10:14
  • @Someprogrammerdude index[i][j] is allocated by the `strdup` function. Regarding the cast before malloc, while I know it's a repetition my uni professor insists on us using it -.- – NotTheNSA Nov 09 '18 at 10:20
  • @joop I had to use *** because it was the objective of the exercise. – NotTheNSA Nov 09 '18 at 10:21
  • I phrased my first comment wrong... You have allocated memory for `index` and `index[i][j]`, but where do you allocate memory for `index[i]`? You have `index` which is a `char ***` and you allocate memory for that with `malloc`. You have `index[i]` which is a `char **`, which we don't see any allocation for. And you have `index[i][j]` which is a `char *` and you allocate memory for with `strdup`. – Some programmer dude Nov 09 '18 at 10:22
  • @Someprogrammerdude you are absolutely right I forgot to add it. I'll edit it now – NotTheNSA Nov 09 '18 at 10:27
  • Throw all stars away. Instead, allocate a 2D array of character pointers: `char* (*arr)[col] = malloc( sizeof(char* [row][col]) );` then allocate each individual string with `arr[i][j] = malloc(...);`. Actually, I doubt you even need 2 dimensions...? Copy pointers from the arrays to merge using memcpy, and then finally qsort it all. That's quite straight-forward to code without being a three star programmer. As for the fastest possible implementation, you should drop the array in favour of either a hash table or a binary tree, depending on the number of items. – Lundin Nov 09 '18 at 14:06

1 Answers1

0

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)) {
         ...
     }
}
Support Ukraine
  • 42,271
  • 4
  • 38
  • 63