Why does my character sorting program produce wrong answers?

Question

I am trying to create a program in C, in which a user inserts random strings into a matrix. The program then uses this formula to evaluate each string and the rest of the code to display the string with the highest value. Every subsequent letter has a bigger value than the previous one.

I would be very glad if someone could point me in the right direction with this, currently the program displays some random letters from the strings.

Formula: Sum=(t*26^(n-1))

t = number of the letter, n = number of letters remaining

Example: abc -> 1*26^2+2*26^1+3*26^0

The rest of the code:

#include <stdio.h>
#include <string.h>
void insert(int, char[10][10], int num[]);
int computing(char[10]);
void sort(int, int num[], char[10][10]);
int main(){
    int x;
    char arr[10][10];
    int num[x];
    printf("How many words do you wish to enter: \n");
    scanf(" %d", &x);
    insert(x, arr, num);
    sort(x, num, arr);
return 0;
}
void insert(int x, char arr[10][10], int num[]){
    int i, r;
    for(i=0; i<x; i++){
        printf("Insert %d. word: ", i+1);
        scanf("%s", &arr[i][0]);
        num[i] = computing(arr[i]);
    }
}
int computing(char arr[10]){
    int n, i, t=1, m=0, k;
    n = strlen(arr);
    k = n;
    for(i=0; i<n; i++){ 
        m += (t*26^(k-1));
        t++;
        k = k - 1;
    }
return m;
}
void sort(int x, int num[], char arr[10][10]){
    int i, temp;
    char ch;
        for(i = 0; i < x - 1; i++){
            if(num[i] > num[i+1]){
                temp = num[i];
                num[i] = num[i+1];
                num[i+1] = temp;
        
                ch = arr[i][0];
                arr[i][0] = arr[i+1][0];
                arr[i+1][0] = ch;
            }
        }
    printf("Word with the biggest sum is: %s\n", &arr[x-1][0]);
}

Are you under the impression that the `^` operator is exponentiation (i.e., that `26^(k-1)` is raising 26 to the power of k-1)? Because it ain't ... it's an Exclusive Or (bitwise) operator. — Adrian Mole, Dec 03 '21 at 20:21
In fact, C doesn't have an exponentiation operator. [The most efficient way to implement an integer based power function pow(int, int)](https://stackoverflow.com/q/101439/10871073). — Adrian Mole, Dec 03 '21 at 20:26
Also, the scanf format should be "%c" or "%1s". The "%s" will look for multiple characters terminated by whitespace, I believe. — Mark Lavin, Dec 03 '21 at 20:28
Note that your function `computing(char arr[10])` doesn't use any of the actual characters in the string, so all strings of the same length will have the same 'value'. The example using `"abc"` is a poor one, because it doesn't disambiguate *"t = number of the letter"*. Also, are you sure that `int` can hold this power-based value? — Weather Vane, Dec 03 '21 at 20:29
`int num[x];` is _above_ the `scanf(" %d",&x);` so `x` is _uninitialized_. Move the `int num[x];` _below_ the `scanf` — Craig Estey, Dec 03 '21 at 20:40
Your `sort` is broken. Even with the noted fixes, it corrupts an entry on test data I provided. — Craig Estey, Dec 03 '21 at 20:44

Craig Estey · Accepted Answer · 2021-12-03T21:21:13.243

Issues:

^ is not the power function
int num[x]; is above the scanf(" %d",&x); so x is uninitialized. Move the int num[x]; below the scanf
The sort is broken. Even with the noted fixes, it corrupts an entry on test data I provided.
The sort needs to perform N passes over the data. As present, it only does one.
arr is hardwired at char arr[10][10];. It should be dynamic like num as: char arr[x][10];

It's much easier to define a struct that has both the word string (in arr) and its num score. Then, the sort doesn't have to swap two arrays only one.

So, I refactored the code to use such a struct and fixed the sort and the other issues. It is annotated:

#include <stdio.h>
#include <string.h>

typedef struct {
    int num;                            // ranking
    char str[10];                       // word string
} word_t;

void insert(int, word_t num[]);
int computing(word_t *);
void sort(int, word_t num[]);

int
main(void)
{
    int x;
// NOTE/BUG: x is _not_ yet initialized
#if 0
    char arr[10][10];
    int num[x];
#endif

    printf("How many words do you wish to enter: \n");
    scanf(" %d", &x);

// NOTE/FIX: x is now initialized
#if 1
    word_t words[x];
#endif

    insert(x, words);

    sort(x, words);

    return 0;
}

void
insert(int x, word_t *words)
{
    int i;

    for (i = 0; i < x; i++) {
        word_t *word = &words[i];

        printf("Insert %d. word: ", i + 1);
        scanf("%s", word->str);

        word->num = computing(word);
        printf("DEBUG: num=%d '%s'\n",word->num,word->str);
    }
}

int
computing(word_t *word)
{
    int n, i,
        t = 1,
        m = 0,
        k;

    n = strlen(word->str);
    k = n;

// NOTE/FIX: compute pow(26,k - 1);
#if 1
    int p26 = 1;
    for (i = 1; i <= (k - 1); ++i)
        p26 *= 26;
#endif

    for (i = 0; i < n; i++) {
#if 0
        m += (t * 26 ^ (k - 1));
#else
        m += (t * p26);
#endif
        t++;

        k = k - 1;
// NOTE/FIX: recalc pow(26,k - 1) now that we've decremented k
#if 1
        p26 /= 26;
#endif
    }

    return m;
}

void
sort(int x, word_t *words)
{
    int i;
    word_t temp;
    int more = 1;

    while (more) {
        more = 0;

        for (i = 0; i < x - 1; i++) {
            word_t *lhs = &words[i];
            word_t *rhs = &words[i + 1];

            if (lhs->num > rhs->num) {
                temp = *lhs;
                *lhs = *rhs;
                *rhs = temp;
                more = 1;
            }
        }
    }

    printf("Word with the biggest sum is: %s\n", words[x - 1].str);
}

Here is the input data I used:

7
abc
defg
hijkl
mnopqr
hello
world
gbye

Note that in the original code, the program printed out mbye as the answer

Here is the program output:

How many words do you wish to enter:
Insert 1. word: DEBUG: num=731 'abc'
Insert 2. word: DEBUG: num=19010 'defg'
Insert 3. word: DEBUG: num=494265 'hijkl'
Insert 4. word: DEBUG: num=12850896 'mnopqr'
Insert 5. word: DEBUG: num=494265 'hello'
Insert 6. word: DEBUG: num=494265 'world'
Insert 7. word: DEBUG: num=19010 'gbye'
Word with the biggest sum is: mnopqr

A possible future issue/fix. Note that the num value is the same for both hello and world. If we're going to the trouble to raise a number to a power, should these numbers be different?

Why does my character sorting program produce wrong answers?

1 Answers1