Using qsort for character array in C

user1527227 picture user1527227 · Apr 18, 2014 · Viewed 14.3k times · Source

I'm trying to use qsort to sort a character array. I can't see why this is not working. I have a pointer to the compare function as the man pages specifies. Can someone please tell me what's wrong? Thanks. My code:

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

int cmpfunc( const void *a, const void *b) {
  return *(int*)a - *(int*)b;
}

void AlphabetSoup( char str[] ) {
  qsort(str, (size_t) strlen(str), (size_t) sizeof(char), cmpfunc);
  printf("%s\n", str);
}


int main() {
  char str1[] = "bcead";

  AlphabetSoup(str1);

  return 0;
}

outputs: dabce when I expect abcde.

Answer

R Sahu picture R Sahu · Apr 18, 2014

Simple error.

Use char* instead of int* in cmpfunc.

int cmpfunc( const void *a, const void *b) {
  return *(char*)a - *(char*)b;
}

When you use int*, instead of char*, the address pointed to by a is interpreted as an address to an int, not a char.

Your input has the following characters:

+---+---+---+---+---+
| b | c | e | a | d |
+---+---+---+---+---+

In hex, those are:

+----+----+----+----+----+
| 62 | 63 | 65 | 61 | 64 |
+----+----+----+----+----+
^    ^
|    |
a    b

If you treat the addresses pointed to a and b as int*, assuming an int takes 4 bytes in your system, *(int*)a can be either

0X62*2^24 + 0X63*2^16 + 0X65*2^8 + 0X61

or

0X62 + 0X63*2^8 + 0X65*2^16 + 0X61*2^24

depending on whether you have big endian system or a little endian system.

You can similarly compute what *(int*)b would be. As you can see, you are already running into unexpected number comparisons. By the time you start comparing the values that are at other byte locations of your input, you are also using memory that you are not supposed to use, and you are reaching the realms of undefined behavior.