Why doesn't this code sort lines containing numbers correctly?

Question

I'm looking at this program that reads input lines and then sorts them, from K&R.

And I can't figure out why it doesn't sort them correctly if I enter for example

1234532 first line
abc second line

It won't sort them in increasing order. Basically it doesn't work if the input lines contains numbers or something other then letters, I think.

But this works for lines with letters:

abc
abcsda

will get sorted correctly.

This is the code:

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

#define MAXLINES 5000

char *lineptr[MAXLINES];

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

int main(int argc, char *argv[])
{
     int nlines;

     if((nlines = readlines(lineptr, MAXLINES)) >= 0) {
          qsort(lineptr, 0, nlines-1);
          writelines(lineptr, nlines);
          system("PAUSE");
          return 0;
     } 
     else {
          printf("error: input too big to sort\n");
          return 1;
     }


  system("PAUSE");  
  return 0;
}


#define MAXLEN 1000
int getline(char *, int);
char *alloc(int);

int readlines(char *lineptr[], int maxlines)
{
    int len, nlines;
    char *p, line[MAXLEN];

    nlines = 0;
    while((len = getline(line, MAXLEN)) > 0)
       if(nlines >= maxlines || (p = alloc(len)) == NULL)
          return -1;
       else {
            line[len-1] = '\0';
            strcpy(p, line);
            lineptr[nlines++] = p;
       }
    return nlines;
}

void writelines(char *lineptr[], int nlines)
{
     while(nlines -- > 0)
         printf("%s\n", *lineptr++);
}

int getline(char s[], int lim)
{
  int c, i;

  for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
    s[i] = c;                                                         
  if (c == '\n') {
    s[i++] = c;   
  }
  s[i] = '\0';
  return i;
}

#define ALLOCSIZE 10000

static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;

char *alloc(int n)
{
     if(allocbuf + ALLOCSIZE - allocp >= n) {
          allocp +=n;
          return allocp - n;
     }
     else 
          return 0;
}

void swap(char *v[], int i, int j)
{
     char *temp;

     temp = v[i];
     v[i] = v[j];
     v[j] = temp;
}

void qsort(char *v[], int left, int right) {

    int i, last;

    if(left >= right) 
       return;

    swap(v, left, (left+right)/2);
    last = left;

    for(i = left + 1; i <= right; i++)
      if(strcmp(v[i], v[left]) < 0)
         swap(v, ++last, i);

    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

Answer 1

It is sorting them correctly. Numbers sort before letters in ASCII. What output are you expecting?

Answer 2

It does the comparison with strcmp(), so it compares individual characters. If you want to compare numbers, you'd need to add an option to (attempt to) convert as much of the beginning of the line as possible to a number and compare the converted numbers when you do the sort (and decide how to treat lines that start with anything other than a digit).

Answer 3

What do you think the correct ordering is? You're probably getting confused by exactly what lexicographic ordering on strings is. From this perspective the correct ordering of

1234532 first line
abc second line

is

1234532 first line
abc second line

because 1 comes before a in ASCII. I have a previous answer on this topic.

Answer 4

If you want to sort strictly on line length, you'll need to make a comparison function to do that and pass it to qsort().

Answer 5

I have an another question! The follow-up exercise asks for:

Rewrite readlines to store lines in an array supplied by main , rather than calling alloc to maintain storage. How much faster is the program?

So i did it this way:

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

#define MAXLINES 5000

char *lineptr[MAXLINES];

int readlines(char *lineptr[], int nlines, char buf[]);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

#define MAXSIZE 10000
int main(int argc, char *argv[])
{
     int nlines;
     char buf[MAXSIZE];

     if((nlines = readlines(lineptr, MAXLINES, buf)) >= 0) {
          qsort(lineptr, 0, nlines-1);
          writelines(lineptr, nlines);
          getchar();
          return 0;
     } 
     else {
          printf("error: input too big to sort\n");
          getchar();
          return 1;
     }

}


#define MAXLEN 1000
int getline(char *, int);

int readlines(char *lineptr[], int maxlines, char buf[])
{
    int len, nlines;
    char *p = buf;
    char line[MAXLEN];

    nlines = 0;
    while((len = getline(line, MAXLEN)) > 0)
       if(nlines >= maxlines || MAXSIZE + buf - p < len)
          return -1;
       else {
            line[len-1] = '\0';
            strcpy(p, line);
            lineptr[nlines++] = p;
            p+=len;
       }

    return nlines;
}

void writelines(char *lineptr[], int nlines)
{
     while(nlines-- > 0)
         printf("%s\n", *lineptr++);
}

int getline(char s[], int lim)
{
  int c, i;

  for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
    s[i] = c;                                                         
  if (c == '\n') {
    s[i++] = c;   
  }
  s[i] = '\0';
  return i;
}

void swap(char *v[], int i, int j)
{
     char *temp;

     temp = v[i];
     v[i] = v[j];
     v[j] = temp;
}

void qsort(char *v[], int left, int right) {

    int i, last;

    if(left >= right) 
       return;

    swap(v, left, (left+right)/2);
    last = left;

    for(i = left + 1; i <= right; i++)
      if(strcmp(v[i], v[left]) < 0)
         swap(v, ++last, i);

    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

Im interested if this is what the author asked for or did i do it wrong.

Also, measuring time diffrence, is it correct to just start the clock at the begining of the main and then stop it after reading lines is over, and compare the time taken?