Exercise 5.14 - sorting in reverse (decreasing) order¶
Question¶
Modify the sort program to handle a -r flag, which indicates sorting in reverse (decreasing) order. Be sure that -r works with -n.
/* Modify the sort program to handle a -r flag, which indicates sorting in
reverse ( decreasing) order. Be sure that -r works with -n */
#include<stdio.h>
#include<string.h>
#define NUMERIC 1 /* numeric sort */
#define DECR 2 /* sorts in decreasing order */
#define LINES 100 /* max # of lines to be sorted */
int numcmp(char *, char *);
int readlines(char *lineptr[], int maxlines);
void myqsort(void *v[], int left, int right, int (*comp)(void *, void *));
void writelines(char *lineptr[], int nlines, int decr);
static char option = 0;
/* sort input lines */
int main(int argc, char *argv[]) {
char *lineptr[LINES];
int nlines; /* pointer to text lines */
int c, rc = 0; /* number of input lines read */
while (--argc > 0 && (*++argv)[0] == '-')
while (c = *++argv[0])
switch (c) {
case 'n': /* numeric sort */
option |= NUMERIC;
break;
case 'r': /* sort in decreasing order */
option |= DECR;
break;
default:
printf("sort:illegal option %c\n", c);
argc = 1;
rc = -1;
break;
}
if (argc)
printf("Usage: sort -nr \n");
else if ((nlines = readlines(lineptr, LINES)) > 0) {
if (option & NUMERIC)
myqsort((void **) lineptr, 0, nlines - 1, (int (*)(void *, void *)) numcmp);
else
myqsort((void **) lineptr, 0, nlines - 1, (int (*)(void *, void *)) numcmp);
writelines(lineptr, nlines, option & DECR);
} else {
printf("input too big to sort \n");
rc = -1;
}
return rc;
}
/* writelines: write output lines */
void writelines(char *lineptr[], int nlines, int decr) {
int i;
if (decr) /* print in decreasing order */
for (i = nlines - 1; i >= 0; i--)
printf("%s\n", lineptr[i]);
else
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}
#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;
}
#define MAXLEN 1000 /* max length of any input line */
int mgetline(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 = mgetline(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;
}
#define ALLOCSIZE 1000 /* 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) {
allocp += n;
return allocp - n;
} else
return 0;
}
void afree(char *p) /* free storage pointed to by p */
{
if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
allocp = p;
}
/* myqsort: sort v[left] ... v[right] into increasing order */
void myqsort(void *v[], int left, int right, int (*comp)(void *, void *)) {
int i, last;
void swap(void *v[], int, int);
if (left >= right)
return;
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, i);
swap(v, left, last);
myqsort(v, left, last - 1, comp);
myqsort(v, last + 1, right, comp);
}
void swap(void *v[], int i, int j) {
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
/* mgetline: read a line into s, return length */
int mgetline(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;
}
Explanation¶
This program when executed with flags -nr and when given an input in any order will sort the arguments and print the numbers in reverse order.
For .e.g, when given an input
$ ./mysort -nr
10
40
242
42
52
The output was:
242
52
42
40
10
The program works by implementing a version of quicksort. In quicksort, we give two indices, left value (starting 0) and right value (nlines, the number of lines), we send the array of strings (char *lineptr[]) to be sorted and then we send a comparator function as a pointer too.
The declartion of myqsort looks like this.
void myqsort(void *v[],int left,int right,int (*comp)(void *,void *));
The comparator function, numcmp will return -1, if the first argument is less than second, it will return 1, if the first argument is greater, otherwise it will 0. This is a standard way in which many comparator functions are defined.
In the execution of quicksort, it partitions the array into 2, and recursively, sorts the left half and then the right half.
Since we have to sort it “in-place”, the details of the implementation needs careful analysis.
We choose the middle element and move it to extreme left (position 0), the compare the values, starting with next element (at position 1) upto our right pointer, the middle of the array.
If we find any values which are less than our element (position 0), we swap it to left, next to our left element and keep that counter as the last value.
Thus for all the values less then our first element, we might have moved them to left.
For e.g.
If our first iteration starts like this.
40 45 55 30 10 60
^
left
Our first few iterations will be:
40 30 45 55 10 60
^ ^
left last
40 30 10 45 55 60
^ ^
left last
And then finally we swap the left and last:
10 30 40 45 55 60
^ ^
last left
Thus we have a partially sorted left side. Thus by carefully moving the pointers we sorted the left side comparing each element with the middle element. Similarly, we do the same for the right half of the array, and then recursively divide each half to sort it.
The curx of the program is in myqsort` function and once that is sorted, the program displays the output as we desire.