Commit | Line | Data |
---|---|---|
cb8c26cc TL |
1 | |
2 | Write a program to read a list of positive numbers | |
3 | and sort them into ascending order. Print | |
4 | the sorted list of numbers one per line | |
5 | as five digit numbers (%5d in printf). | |
6 | Stop reading numbers when getnum returns zero. | |
7 | Compile and test your program; then type "ready". | |
8 | #once #create Ref | |
9 | 1 | |
10 | 3 | |
11 | 4 | |
12 | 9 | |
13 | 11 | |
14 | 12 | |
15 | 13 | |
16 | 14 | |
17 | 15 | |
18 | 16 | |
19 | 17 | |
20 | 20 | |
21 | 34 | |
22 | 71 | |
23 | 200 | |
24 | 225 | |
25 | 250 | |
26 | 275 | |
27 | 300 | |
28 | 4095 | |
29 | 7111 | |
30 | 16384 | |
31 | #once cp %s/getnum.o . | |
32 | #once #create input | |
33 | 4 20 3 200 16384 4095 71 11 12 13 14 | |
34 | 15 16 17 34 9 7111 300 275 250 225 1 | |
35 | #user | |
36 | a.out <input >xxx | |
37 | #cmp xxx Ref | |
38 | #succeed | |
39 | main() | |
40 | { | |
41 | getlist(); | |
42 | sortlist(); | |
43 | printlist(); | |
44 | } | |
45 | ||
46 | int n; | |
47 | int list[1000]; | |
48 | ||
49 | getlist() | |
50 | { | |
51 | while (list[n]=getnum()) | |
52 | n++; | |
53 | } | |
54 | ||
55 | sortlist() | |
56 | { | |
57 | shellsort(list,n); | |
58 | } | |
59 | ||
60 | /* this is a shell sort, stripped down to process a list | |
61 | of integers only. Although you probably don't know | |
62 | how to write this offhand, you should know where to find | |
63 | it - it is only marginally more code than a bubble sort | |
64 | and much faster (n**1.5 vs. n**2) in time. */ | |
65 | shellsort(array, nitem) | |
66 | int *array; | |
67 | shellsort(v, n) /* sort v[0]...v[n-1] into increasing order */ | |
68 | int v[], n; | |
69 | { | |
70 | int gap, i, j, temp; | |
71 | ||
72 | for (gap = n/2; gap > 0; gap /= 2) | |
73 | for (i = gap; i < n; i++) | |
74 | for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) { | |
75 | temp = v[j]; | |
76 | v[j] = v[j+gap]; | |
77 | v[j+gap] = temp; | |
78 | } | |
79 | } | |
80 | ||
81 | printlist() | |
82 | { | |
83 | int i; | |
84 | for(i=0; i<n; i++) | |
85 | printf("%5d\n",list[i]); | |
86 | } | |
87 | /* this is a crummy bubble sort which | |
88 | would work perfectly well for this | |
89 | problem but can not be recommended | |
90 | for large jobs. | |
91 | sortlist() | |
92 | { | |
93 | int i, j, k; | |
94 | ||
95 | for(i=0; i<n; i++) | |
96 | for(j=n-1; j>0; j--) | |
97 | if (list[j-1] > list[j]) { | |
98 | k = list[j]; | |
99 | list[j] = list[j-1]; | |
100 | list[j-1] = k; | |
101 | } | |
102 | } | |
103 | ****/ | |
104 | #log | |
105 | #next | |
106 | 30.1a 10 |