LSD Radix for a fixed count array

Question

I would like to create a radix LSD to sort strings. I tried to adapt to a count[27] instead of count[256], because the exercise requires it. I must use A[I][d] - 'a' + 1 for [a-z] and 0 for spaces, but it is not sorting correctly. Some strings on my tests have been duplicated. How can I solve this?

#define MAX 15
void foo(char** A, int n, int k, int max) {
  int i, d;
  char** B = (char**)malloc(sizeof(char*) * n);

  for(i = 0; i < n; i++)
    B[i] = (char*)malloc(sizeof(char) * max);

  for (d = max - 1; d >= 0; d--) {
    int* count = (int*)malloc(sizeof(int) * k);
    
    for(i = 0; i < k; i++)
      count[i] = 0;

    for (i = 0; i < n; i++) {
      if(A[i][d] == 32) count[0]++;
      else count[A[i][d] - 'a' + 1]++;
    }

    for (i = 1; i < k; i++)
      count[i] += count[i - 1];
    
    for (i = n - 1; i >= 0; i--) {
      if(A[i][d] == 32) {
        strcpy(B[count[0] - 1], A[i]);
        count[0]--;
      }
      else {
        strcpy(B[count[A[i][d] - 'a' + 1] - 1], A[i]);
        count[A[i][d]]--;
     }
    }

    for (i = 0; i < n; i++)
      strcpy(A[i], B[i]);

    free(count);
  }

  for(i = 0; i < n; i++) free(B[i]);
  free(B);
}

What are the validity constraints on the sort inputs? Can there be characters other than spaces and upper- and lowercase ASCII letters? If so, then how are those supposed to affect the ordering? — John Bollinger
– John Bollinger, Commented Apr 19, 2024 at 15:03
And can there in fact be spaces in the inputs, other than as separators? If so, then your method of input will not handle that, plus you have a likely issue with distinguishing between trailing spaces and trailing nothing. If not, then why are you doing any space-related processing at all? If you're to use exactly 27 distinct digit values with varying-length strings, then I'm inclined to guess that the 27th is supposed to be for no-character, as opposed to for the space character. — John Bollinger
– John Bollinger, Commented Apr 19, 2024 at 15:07
Is MAX supposed to be the maximum number of significant characters in any input? If so, then main() is not allocating enough space for its inputs. Each one needs an extra byte for a string terminator. — John Bollinger
– John Bollinger, Commented Apr 19, 2024 at 15:19
Re "Some strings on my tests have been duplicated.", You didn't demo your problem. Provide a test for which it fails! — ikegami
– ikegami, Commented Apr 19, 2024 at 15:36
Why are you doing all those strcpy() in the sort function? You structure the data as an array of pointers, so all you need to do is assign pointers. — John Bollinger
– John Bollinger, Commented Apr 19, 2024 at 15:50

John Bollinger · Accepted Answer · 2024-04-19 17:36:37Z

2

There are lots of stylistic and efficiency issues with the program, but I found only three actual errors:

You rely on the values of all the elements of each A[i], but you do not reliably set all of them. Specifically, malloc() does not initialize the memory it allocates, and scanf() does not write any bytes past the string terminator. You could fix this by allocating via calloc() instead of malloc().
You do not allocate enough space for your strings in the first place. You rely on there being space for MAX characters plus a string terminator, but you allocate space only for MAX characters.
(Likely the issue responsible for the observed misbehavior) your sort function does not manage its count array correctly. Specifically, this is wrong:
```
        count[A[i][d]]--;
```
It should be
```
        count[A[i][d] - 'a' + 1]--;
```

answered Apr 19, 2024 at 17:36

John Bollinger

191k11 gold badges103 silver badges206 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

megarubber Over a year ago

Thanks! I adjusted count[] and MAX here.

Collectives™ on Stack Overflow

LSD Radix for a fixed count array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related