1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#include <stdio.h>
#include <string.h>
// An extremely simple allocation system.
// Memory must be freed in the reverse order it was allocated.
// #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 NULL;
// }
// }
// void afree(char *p) {
// if (p >= allocbuf && p < allocbuf + ALLOCSIZE) {
// allocp = p;
// }
// }
#define MAXLINES 5000
int readlines(char* lineptr[], int nlines);
void writelines(char* lineptr[], int nlines);
void qsort(char* lineptr[], int left, int right);
int main() {
int nlines;
char* lineptr[MAXLINES];
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
qsort(lineptr, 0, nlines-1);
writelines(lineptr, nlines);
return 0;
} else {
fprintf(stderr, "error: input too big to sort\n");
return 1;
}
}
#define MAXLEN 1000
int z_getline(char*, int);
// char* alloc(int);
int readlines(char* lineptr[], int maxlines) {
int len;
int nlines = 0;
char* p;
char line[MAXLEN];
while ((len = z_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;
}
void writelines(char* lineptr[], int nlines) {
for (int i=0; i<nlines; i++)
printf("%s\n", lineptr[i]);
}
void swap(char* v[], int i, int j);
void qsort(char* v[], const int left, const 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);
}
void swap(char* v[], int i, int j) {
char* temp = v[i];
v[i] = v[j];
v[j] = temp;
}
/* getline: read a line into s, return length */
int z_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;
++i;
}
s[i] = '\0';
return i;
}
|
