Return to L20.1a CVS log

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

Annotation of 42BSD/usr.lib/learn/C/L20.1a, revision 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.