Return to L20.1a CVS log

Up to [CSRG BSD Unix] / 43BSD / usr.lib / learn / C

Annotation of 43BSD/usr.lib/learn/C/L20.1a, revision 1.1.1.1

1.1       root        1: #print
                      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 -1.
                      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:        int n;
                     42:        int list[1000];
                     43: 
                     44:        n = getlist(list);
                     45:        shellsort(list, n);
                     46:        printlist(list, n);
                     47: }
                     48: 
                     49: getlist(list)
                     50: int list[];
                     51: {
                     52:        int n;
                     53: 
                     54:        n = 0;
                     55:        while ((list[n]=getnum()) >= 0)
                     56:                n++;
                     57:        return(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(v, n)  /* sort v[0]...v[n-1] into increasing order */
                     66: int v[], n;
                     67: {
                     68:     int gap, i, j, temp;
                     69: 
                     70:     for (gap = n/2; gap > 0; gap /= 2)
                     71:         for (i = gap; i < n; i++)
                     72:             for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
                     73:                 temp = v[j];
                     74:                 v[j] = v[j+gap];
                     75:                 v[j+gap] = temp;
                     76:             }
                     77: }
                     78: 
                     79: printlist(list, n)
                     80: int list[], n;
                     81: {
                     82:        int i;
                     83:        for(i=0; i<n; i++)
                     84:                printf("%5d\n",list[i]);
                     85: }
                     86: /* this is a crummy bubble sort which
                     87:    would work perfectly well for this
                     88:    problem but can not be recommended
                     89:    for large jobs. 
                     90: sortlist()
                     91: {
                     92:        int i, j, k;
                     93: 
                     94:        for(i=0; i<n; i++)
                     95:                for(j=n-1; j>0; j--)
                     96:                        if (list[j-1] > list[j]) {
                     97:                                k = list[j];
                     98:                                list[j] = list[j-1];
                     99:                                list[j-1] = k;
                    100:                        }
                    101: }
                    102:  ****/
                    103: #log
                    104: #next
                    105: 30.1a 10

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.