Search code examples
carrayssortingpointersquicksort

Qsort removes first element from array (char *)


I am very new to C and I am trying to use qsort() with an array of char pointers. It is not sorting the array alphabetically as I expected and it removes the first element. I have tried adjusting all of the arguments including the comparison function but I have been unable to figure out what is wrong.

Enter word: foo
Enter word: bar
Enter word: baz
Enter word: quux

Expected:
bar
baz
foo
quux

Result:

bar
baz
quux

My Code:

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

#define MAX_WORDS 10
#define MAX_LENGTH 20

int read_line(char str[], int n);
int compare(const void *a, const void *b);

int main(void) {
  char *words[MAX_WORDS], word[MAX_LENGTH + 1];
  int i;

  for(i = 0; i < MAX_WORDS; i++) {
    printf("Enter word: ");
    read_line(word, MAX_LENGTH);

    words[i] = malloc(strlen(word) + 1);
    if(!words[i]) {
      printf("Allocation of memory failed...\n");
      exit(EXIT_FAILURE);
    }

    strcpy(words[i], word);

    if(!strlen(words[i]))
      break;
  }

  qsort(words[0], i, sizeof(char *), compare);

  for(int j = 0; j <= i; j++) {
    printf("%s\n", words[j]);
  }

  return 0;
}

int read_line(char str[], int n) {
  int ch, i;

  while((ch = getchar()) != '\n') {
    if(i < n)
      str[i++] = ch;
  }
  str[i] = '\0';

  return i;
}

int compare(const void *a, const void *b) {
  return strcmp((char *) a, (char *) b);
}

Solution

  • Three errors.

    1. qsort requires a pointer to the first element of the array being sorted.

      Replace

      qsort(words[0], i, sizeof(char *), compare);
      

      with

      qsort(&( words[0] ), i, sizeof(char *), compare);
      

      or just

      qsort(words, i, sizeof(char *), compare);
      

      This latter version works because an array used where a pointer is expected decays into a pointer to its first element.

    2. The compare function is passed pointers to the elements of the array being sorted. Since you are sorting an array of pointers, that means the compare function is passed pointers to those pointers (char**) in your case. As such, compare should be

      static int compare(const void *a, const void *b) {
        return strcmp(*(char **)a, *(char **)b);
      }
      

      Even better:

      static int compare(const void *a, const void *b) {
        return strcmp(*(char * const *)a, *(char * const *)b);
      }
      
    3. Your final loop has one too many passes.

      If i<MAX_WORDS (because a blank line was entered), this will cause a blank line to be emitted (because words[i] contains a zero-length string). If i==MAX_WORDS, this invokes Undefined Behaviour (because words[i] is beyond the end of the array).

      Replace

      for(int j = 0; j <= i; j++)
      

      with

      for(int j = 0; j < i; j++)