unix program

[pacman169]

Hello I'm getting unexpected results when running this program on command line/terminal window. This should sort input lines in alphabetical order, and if an optional argument -n is given sort them numerically.

Some results with ./fast -n
abcdefg
abcd
abc

abcd

abc
abcdefg


I have been thinking this for days, why this sorts them like this, and not in increasing order.

Here is the program(straight from book, almost)

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

#define MAXLINES 5000      /* max #lines to be sorted */
char *lineptr[MAXLINES];  /* pointers to text lines */

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


void quicksort(void *lineptr[], int left, int right, int (*comp)(void *, void *));
int numcmp( const char *,  const char *);


/* sort input lines */

int main(int argc, char *argv[])
{
	
	int nlines;     /* number of input lines read */
	int numeric = 0;   /* 1 if numeric sort */
	
	if (argc > 1 && strcmp(argv[1], "-n") == 0)        
	    numeric = 1;
	
	if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
		quicksort((void **) lineptr, 0, nlines-1, (int (*)(void *, void *)) (numeric ? numcmp : strcmp));
		writelines(lineptr, nlines);
		return 0;
	}  else {
		printf("input too big to sort\n");
		return 1;                                   
		
	}
	
}


  


/* qsort: sort v[left]...v[right] into increasing order */

void quicksort(void *v[], int left, int right, int (*comp) (void *, void*))
	
  {
	  
	  int i, last;
	  void myswap(void *v[], int, int);
	  
	  if (left >= right)     /* do nothing if array contains */
		  return;            /* fewer than two elements */
	  myswap(v, left, (left + right)/2);
	  last = left;
	  for (i = left+1; i<= right; i++)
		  if ((*comp) (v[i], v[left]) < 0)
			 myswap(v, ++last, i);
	  myswap(v, left, last);
	  quicksort(v, left, last-1, comp);
	  quicksort(v, last+1, right, comp);
	  
  }
  
  
  
  /* numcmp:  compare s1 and s2 numerically */
  
  int numcmp( const char *s1, const 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;
	  
  }
  
  
  void myswap(void *v[], int i, int j)
  {
	  void *temp;
	  
	  temp = v[i];
	  v[i] = v[j];
	  v[j] = temp;
	  
  }
  
  
  
  
#define MAXLEN 1000    /* max length of any input line */
int mygetline(char *, int);
char *alloc(int);

  /* readlines: read input lines */
  
  int readlines(char *lineptr[], int maxlines)
  {
	  int len, nlines;
	  char *p, line[MAXLEN];
	  
	  nlines = 0;
	  while ((len = mygetline(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;
  }
  
  
  void writelines(char *lineptr[], int nlines)
  {
  	int i;
	
	
  	for (i = 0; i < nlines; i++)
  		printf("%s\n", lineptr[i]);
	
  }
  
  
  int mygetline (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;
  		++i;
  	}
  	s[i] = '\0';
  	return i;
	
  }
  
  
	
	
	
  #define ALLOCSIZE 10000 /* size of available space */

  static char allocbuf[ALLOCSIZE];   /* storage for alloc */
  static char *allocp = allocbuf;    /* next free position */

  char *alloc(int n)   /* return pointer to n characters */
  {
	
  	if (allocbuf + ALLOCSIZE - allocp >= n) {  /* it fits */
  		allocp += n;
  		return allocp - n; /* old p */
  	}  else               /* not enough room */
  		return 0;
  }
		
 

[kbw]

and if an optional argument -n is given sort them numerically.

Some results with ./fast -n

The numeric value of all those strings to be sorted is zero. So what do you think the output should look like.

[pacman169]

Hm, that's true. The program expects arguments of type int. I might even have found this myself x).

Having that said, why are the arguments of numcmp declared as char?

[kbw]

Because the input stream is text. That text is converted to a number with atof() before use.

[pacman169]

This doesn't go with the scope of my original question, but I might well ask it.
What is the purpose of lines 25 and 29? Also the qsort function seems hard to understand.

[kbw]

Lines 25-26: Determine if it needs to do a numeric sort.

Line 28: Read data
Line 29: Sort data

[pacman169]

Wouldn't this if strcmp(argv[1], "-n") == 0
be exactly the same as if (argv[1] == "-n") ?? .
Can't see the need for strcmp here.

I understand that line 29 sorts data but not the line itself with all that pointer fiddling.

[kbw]

argv[i] is of type char*.

"-n" is of type const char*

The == would compare const char*s and that would be a bitwise comparison on the pointers, not the strings they point to.