0

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);
}
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Tool
  • 12,126
  • 15
  • 70
  • 120
  • What order are you expecting for your first example? You should get the numeric line first, then the alpha line. – Fred Larson Jan 05 '10 at 18:46
  • 1
    `qsort()` is declared (correctly) in `stdlib.h` - why are you declaring it again (and incorrectly) in your program? – Chris Lutz Jan 05 '10 at 18:48
  • I tought it was sorting them based on size; 1234123 is larger then abc, so i suppose the abc should be printed out first, not the line with numbers. – Tool Jan 05 '10 at 18:49
  • No, it won't sort on line length unless the lines are equal up to the end of the shorter line. In your case '1' < 'a', so the comparison stops there. – Fred Larson Jan 05 '10 at 18:50
  • @Chris: K&R use their own implementation of qsort: from the errata: *119-121(§5.11): The qsort discussion needs recasting in several ways. First, qsort is a standard routine in ANSI/ISO C, so the rendition here should be given a different name, especially because the arguments to standard qsort are a bit different: the standard accepts a base pointer and a count, while this example uses a base pointer and two offsets.* (http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html) – Alok Singhal Jan 05 '10 at 18:51
  • That sounds just so illogical to me. I mean qsort should sort lines into INCREASING order, thats why i was confused with this. But i understand now, thanks! – Tool Jan 05 '10 at 18:54
  • qsort does sort lines in increasing order, but your definition of "increasing" isn't the same as everybody else's. Why do you think it's more logical to sort strings by length rather than by alphabetical order? – jamesdlin Jan 05 '10 at 19:55

4 Answers4

6

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

Jim Garrison
  • 85,615
  • 20
  • 155
  • 190
5

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.

Community
  • 1
  • 1
jason
  • 236,483
  • 35
  • 423
  • 525
  • Oh well, i tought it compared them based on length, not ASCII value. I guess that explains it. – Tool Jan 05 '10 at 18:51
  • Nope. It works like a dictionary with numbers coming before letters. Check out the Wikipedia article and the previous answer that I linked to. Feel free to ask here if you have additional questions. – jason Jan 05 '10 at 18:54
  • 1
    If you want ordering by length, change `if(strcmp(v[i], v[left]) < 0)` in `qsort()` above to `if (strlen(v[i]) < strlen(v[left]))`. – Alok Singhal Jan 05 '10 at 19:26
0

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).

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
0

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().

Fred Larson
  • 60,987
  • 18
  • 112
  • 174