Trying qsort on K&R "The C Programming Language"

Question

I'm pretty new at this, so I tried compiling the main on page 119 (§5.11) along w/ its dependencies. I managed to get a clean build with this:

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

#define ALLOCSIZE 10000
#define MAXLINES 5000
#define MAXLEN 1000

int getline(char *, int);
char *alloc(int);
char *lineptr[MAXLINES];

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

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

int numcmp(char *, char *);

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


/* getline:  read a line, return length */
int getline(char *line, int max)
{
   if (fgets(line, max, stdin) == NULL)
      return 0;
   else
      return strlen(line);
}


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


/* readlines:  read input lines */
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'; /* delete newline */
         strcpy(p, line);
         lineptr[nlines++] = p;
      }
   return nlines;
}


/* writelines:  write output lines */
void writelines(char *lineptr[], int nlines)
{
   int i;

   for (i = 0; i < nlines; i++)
      printf("%s\n", lineptr[i]);
}


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

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


/* qsort:  sort v[left]...v[right] into increasing order */
void qsort(void *v[], int left, int right,
           int (*comp)(void *, void *))
{
   int i, last;
   void swap(void *v[], int, int);

   if (left >= right)
      right;
   swap(v, left, (left + right)/2);
   last = left;
   for(i = left+1; i <= right; i++)
      if((*comp)(v[i], v[left]) < 0)
         swap(v, ++last, 1);
   swap(v, left, last);
   qsort(v, left, last-1, comp);
   qsort(v, last+1, right, comp);
}


#include <stdlib.h>

/* numcmp:  compare s1 and s2 numerically */
int numcmp(char *s1, char *s2)
{
   double v1, v2;

   v1 = atof(s1);
   v2 = atof(s2);
   if (v1 < v2)
      return -1;
   else if (v1 > v2)
      return 1;
   else
      return 0;
}


/* strcmp01:  return <0 if s<t , 0 if s==t, >0 if s>t */
int strcmp01(char *s, char *t)
{
   for( ; *s == *t; s++, t++)
      if(*s == '\0')
         return 0;
   return *s - *t;
}


/* sort input lines */
main(int argc, char *argv[])
{
   int nlines;
   int numeric = 0;

   if (argc > 1 && strcmp01(argv[1], "-n") == 0)
      numeric = 1;
   if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
      qsort((void **) lineptr, 0, nlines-1,
         (int (*)(void*,void*))(numeric ? numcmp : strcmp01));
      writelines(lineptr, nlines);
      return 0;
   }
   else {
      printf("input too big to sort\n");
      return 1;
   }
}

But when I run it in a DOS Window (Win 7 for what it's worth), the cursor command prompt accepts multiple lines of key entry input, and... . And what exactly? After I type in a few lines of greeking, nothing happens. I just Ctrl C out of it and I'm back to a command prompt.

Alternatively I composed a few lines of stuff into a test.txt file and tried running

[DIR\]mybuild.exe <[DIR\]test.txt

That just throws an error (a Win 7 dialog appears that says "mybuild.exe has stopped working"). It does find the test.txt file; it just "stop[s] working."

What can I do to run this program successfully? (I'm just trying this never having seen it run anywhere before.) Thanks, everyone, for your help.

Answer 1

If you are just trying to test qsort then you could just have an array of strings, and just pass that in, with your known test case.

If you want to read from a file you will need to use something like fopen to open the file:

http://msdn.microsoft.com/en-us/library/z5hh6ee9%28VS.80%29.aspx

Once you open it, you can read in the words using fread.

This example shows opening, writing, reading, closing a file:

http://msdn.microsoft.com/en-us/library/kt0etdcs%28VS.100%29.aspx

I would go with just having a static array though, to start with, just to test out your qsort implementation.

Answer 2

Add some printf()s in strategic places to see what your program is up to.

To start with, try find out whether it is stuck inside readlines(), qsort(), or writelines().

So, add some printf()s to main, just before calling each of those functions. Once you know which of these the computer is stuck in, you can repeat this technique on that function itself, perhaps displaying the value of local variables to help you understand what is happening.

Answer 3

1. press F6 or Ctrl+Z to end the input in a console.

2. by add the fprintf(stderr,...) to your code, i found that the program actually runs out of stack. you probably got the qsort wrong. like

if (left >= right) right;

void qsort(void *v[], int left, int right,
           int (*comp)(void *, void *))
{
   int i, last;
   void swap(void *v[], int, int);

fprintf(stderr, "left %d  right %d\n", left, right);
   if (left >= right)
      right;
   swap(v, left, (left + right)/2);
   last = left;
   for(i = left+1; i <= right; i++)
      if((*comp)(v[i], v[left]) < 0)
         swap(v, ++last, 1);
   swap(v, left, last);
   qsort(v, left, last-1, comp);
   qsort(v, last+1, right, comp);
}

Answer 4

if (left >= right)
    right;

did you mean

if (left >= right)
    return;

?