home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: SHell self-extracting ARchive
(archive/shar).
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| SHell self-extracting ARchive (archive/shar)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| ASCII text
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| fmt/329 Shell Archive Format
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 4e 65 77 73 67 72 6f 75 | 70 73 3a 20 63 6f 6d 70 |Newsgrou|ps: comp|
|00000010| 2e 73 6f 75 72 63 65 73 | 2e 6d 69 73 63 0a 50 61 |.sources|.misc.Pa|
|00000020| 74 68 3a 20 73 70 61 72 | 6b 79 21 6b 65 6e 74 0a |th: spar|ky!kent.|
|00000030| 46 72 6f 6d 3a 20 6d 69 | 6b 65 79 40 6f 6e 74 65 |From: mi|key@onte|
|00000040| 6b 2e 63 6f 6d 20 28 4d | 69 6b 65 20 4c 65 65 29 |k.com (M|ike Lee)|
|00000050| 0a 53 75 62 6a 65 63 74 | 3a 20 20 76 33 34 69 30 |.Subject|: v34i0|
|00000060| 37 34 3a 20 20 66 6c 6f | 67 67 65 72 20 2d 20 53 |74: flo|gger - S|
|00000070| 6f 72 74 20 46 6c 6f 67 | 67 65 72 20 76 30 2e 30 |ort Flog|ger v0.0|
|00000080| 2c 20 50 61 72 74 30 32 | 2f 30 32 0a 4d 65 73 73 |, Part02|/02.Mess|
|00000090| 61 67 65 2d 49 44 3a 20 | 3c 31 39 39 32 44 65 63 |age-ID: |<1992Dec|
|000000a0| 31 38 2e 31 35 32 33 30 | 34 2e 31 30 30 31 38 40 |18.15230|4.10018@|
|000000b0| 73 70 61 72 6b 79 2e 69 | 6d 64 2e 73 74 65 72 6c |sparky.i|md.sterl|
|000000c0| 69 6e 67 2e 63 6f 6d 3e | 0a 46 6f 6c 6c 6f 77 75 |ing.com>|.Followu|
|000000d0| 70 2d 54 6f 3a 20 63 6f | 6d 70 2e 73 6f 75 72 63 |p-To: co|mp.sourc|
|000000e0| 65 73 2e 64 0a 58 2d 4d | 64 34 2d 53 69 67 6e 61 |es.d.X-M|d4-Signa|
|000000f0| 74 75 72 65 3a 20 31 36 | 66 38 37 66 63 65 63 37 |ture: 16|f87fcec7|
|00000100| 39 63 65 31 31 32 30 34 | 36 31 33 33 38 65 37 35 |9ce11204|61338e75|
|00000110| 66 32 61 31 66 63 0a 53 | 65 6e 64 65 72 3a 20 6b |f2a1fc.S|ender: k|
|00000120| 65 6e 74 40 73 70 61 72 | 6b 79 2e 69 6d 64 2e 73 |ent@spar|ky.imd.s|
|00000130| 74 65 72 6c 69 6e 67 2e | 63 6f 6d 20 28 4b 65 6e |terling.|com (Ken|
|00000140| 74 20 4c 61 6e 64 66 69 | 65 6c 64 29 0a 4f 72 67 |t Landfi|eld).Org|
|00000150| 61 6e 69 7a 61 74 69 6f | 6e 3a 20 4f 6e 74 65 6b |anizatio|n: Ontek|
|00000160| 20 43 6f 72 70 6f 72 61 | 74 69 6f 6e 20 2d 2d 20 | Corpora|tion -- |
|00000170| 4c 61 67 75 6e 61 20 48 | 69 6c 6c 73 2c 20 43 61 |Laguna H|ills, Ca|
|00000180| 6c 69 66 6f 72 6e 69 61 | 0a 52 65 66 65 72 65 6e |lifornia|.Referen|
|00000190| 63 65 73 3a 20 3c 63 73 | 6d 2d 76 33 34 69 30 37 |ces: <cs|m-v34i07|
|000001a0| 33 3d 66 6c 6f 67 67 65 | 72 2e 30 39 31 38 31 38 |3=flogge|r.091818|
|000001b0| 40 73 70 61 72 6b 79 2e | 49 4d 44 2e 53 74 65 72 |@sparky.|IMD.Ster|
|000001c0| 6c 69 6e 67 2e 43 4f 4d | 3e 0a 44 61 74 65 3a 20 |ling.COM|>.Date: |
|000001d0| 46 72 69 2c 20 31 38 20 | 44 65 63 20 31 39 39 32 |Fri, 18 |Dec 1992|
|000001e0| 20 31 35 3a 32 33 3a 30 | 34 20 47 4d 54 0a 41 70 | 15:23:0|4 GMT.Ap|
|000001f0| 70 72 6f 76 65 64 3a 20 | 6b 65 6e 74 40 73 70 61 |proved: |kent@spa|
|00000200| 72 6b 79 2e 69 6d 64 2e | 73 74 65 72 6c 69 6e 67 |rky.imd.|sterling|
|00000210| 2e 63 6f 6d 0a 4c 69 6e | 65 73 3a 20 38 30 39 0a |.com.Lin|es: 809.|
|00000220| 0a 53 75 62 6d 69 74 74 | 65 64 2d 62 79 3a 20 6d |.Submitt|ed-by: m|
|00000230| 69 6b 65 79 40 6f 6e 74 | 65 6b 2e 63 6f 6d 20 28 |ikey@ont|ek.com (|
|00000240| 4d 69 6b 65 20 4c 65 65 | 29 0a 50 6f 73 74 69 6e |Mike Lee|).Postin|
|00000250| 67 2d 6e 75 6d 62 65 72 | 3a 20 56 6f 6c 75 6d 65 |g-number|: Volume|
|00000260| 20 33 34 2c 20 49 73 73 | 75 65 20 37 34 0a 41 72 | 34, Iss|ue 74.Ar|
|00000270| 63 68 69 76 65 2d 6e 61 | 6d 65 3a 20 66 6c 6f 67 |chive-na|me: flog|
|00000280| 67 65 72 2f 70 61 72 74 | 30 32 0a 45 6e 76 69 72 |ger/part|02.Envir|
|00000290| 6f 6e 6d 65 6e 74 3a 20 | 55 4e 49 58 0a 0a 23 21 |onment: |UNIX..#!|
|000002a0| 20 2f 62 69 6e 2f 73 68 | 0a 23 20 54 68 69 73 20 | /bin/sh|.# This |
|000002b0| 69 73 20 61 20 73 68 65 | 6c 6c 20 61 72 63 68 69 |is a she|ll archi|
|000002c0| 76 65 2e 20 20 52 65 6d | 6f 76 65 20 61 6e 79 74 |ve. Rem|ove anyt|
|000002d0| 68 69 6e 67 20 62 65 66 | 6f 72 65 20 74 68 69 73 |hing bef|ore this|
|000002e0| 20 6c 69 6e 65 2c 20 74 | 68 65 6e 20 66 65 65 64 | line, t|hen feed|
|000002f0| 20 69 74 0a 23 20 69 6e | 74 6f 20 61 20 73 68 65 | it.# in|to a she|
|00000300| 6c 6c 20 76 69 61 20 22 | 73 68 20 66 69 6c 65 22 |ll via "|sh file"|
|00000310| 20 6f 72 20 73 69 6d 69 | 6c 61 72 2e 20 20 54 6f | or simi|lar. To|
|00000320| 20 6f 76 65 72 77 72 69 | 74 65 20 65 78 69 73 74 | overwri|te exist|
|00000330| 69 6e 67 20 66 69 6c 65 | 73 2c 0a 23 20 74 79 70 |ing file|s,.# typ|
|00000340| 65 20 22 73 68 20 66 69 | 6c 65 20 2d 63 22 2e 0a |e "sh fi|le -c"..|
|00000350| 23 20 43 6f 6e 74 65 6e | 74 73 3a 20 20 49 4e 53 |# Conten|ts: INS|
|00000360| 54 41 4c 4c 41 54 49 4f | 4e 20 4d 61 6b 65 66 69 |TALLATIO|N Makefi|
|00000370| 6c 65 20 62 6f 67 6f 5f | 73 6f 72 74 2e 63 20 62 |le bogo_|sort.c b|
|00000380| 75 62 62 6c 65 5f 73 6f | 72 74 2e 63 0a 23 20 20 |ubble_so|rt.c.# |
|00000390| 20 69 6e 73 65 72 74 5f | 73 6f 72 74 2e 63 20 73 | insert_|sort.c s|
|000003a0| 68 65 6c 6c 5f 73 6f 72 | 74 2e 63 20 73 6f 72 74 |hell_sor|t.c sort|
|000003b0| 69 6e 67 2e 68 0a 23 20 | 57 72 61 70 70 65 64 20 |ing.h.# |Wrapped |
|000003c0| 62 79 20 6b 65 6e 74 40 | 73 70 61 72 6b 79 20 6f |by kent@|sparky o|
|000003d0| 6e 20 54 68 75 20 44 65 | 63 20 31 37 20 31 33 3a |n Thu De|c 17 13:|
|000003e0| 35 30 3a 33 35 20 31 39 | 39 32 0a 50 41 54 48 3d |50:35 19|92.PATH=|
|000003f0| 2f 62 69 6e 3a 2f 75 73 | 72 2f 62 69 6e 3a 2f 75 |/bin:/us|r/bin:/u|
|00000400| 73 72 2f 75 63 62 3a 2f | 75 73 72 2f 6c 6f 63 61 |sr/ucb:/|usr/loca|
|00000410| 6c 2f 62 69 6e 3a 2f 75 | 73 72 2f 6c 62 69 6e 20 |l/bin:/u|sr/lbin |
|00000420| 3b 20 65 78 70 6f 72 74 | 20 50 41 54 48 0a 65 63 |; export| PATH.ec|
|00000430| 68 6f 20 49 66 20 74 68 | 69 73 20 61 72 63 68 69 |ho If th|is archi|
|00000440| 76 65 20 69 73 20 63 6f | 6d 70 6c 65 74 65 2c 20 |ve is co|mplete, |
|00000450| 79 6f 75 20 77 69 6c 6c | 20 73 65 65 20 74 68 65 |you will| see the|
|00000460| 20 66 6f 6c 6c 6f 77 69 | 6e 67 20 6d 65 73 73 61 | followi|ng messa|
|00000470| 67 65 3a 0a 65 63 68 6f | 20 27 20 20 20 20 20 20 |ge:.echo| ' |
|00000480| 20 20 20 20 22 73 68 61 | 72 3a 20 45 6e 64 20 6f | "sha|r: End o|
|00000490| 66 20 61 72 63 68 69 76 | 65 20 32 20 28 6f 66 20 |f archiv|e 2 (of |
|000004a0| 32 29 2e 22 27 0a 69 66 | 20 74 65 73 74 20 2d 66 |2)."'.if| test -f|
|000004b0| 20 27 49 4e 53 54 41 4c | 4c 41 54 49 4f 4e 27 20 | 'INSTAL|LATION' |
|000004c0| 2d 61 20 22 24 7b 31 7d | 22 20 21 3d 20 22 2d 63 |-a "${1}|" != "-c|
|000004d0| 22 20 3b 20 74 68 65 6e | 20 0a 20 20 65 63 68 6f |" ; then| . echo|
|000004e0| 20 73 68 61 72 3a 20 57 | 69 6c 6c 20 6e 6f 74 20 | shar: W|ill not |
|000004f0| 63 6c 6f 62 62 65 72 20 | 65 78 69 73 74 69 6e 67 |clobber |existing|
|00000500| 20 66 69 6c 65 20 5c 22 | 27 49 4e 53 54 41 4c 4c | file \"|'INSTALL|
|00000510| 41 54 49 4f 4e 27 5c 22 | 0a 65 6c 73 65 0a 20 20 |ATION'\"|.else. |
|00000520| 65 63 68 6f 20 73 68 61 | 72 3a 20 45 78 74 72 61 |echo sha|r: Extra|
|00000530| 63 74 69 6e 67 20 5c 22 | 27 49 4e 53 54 41 4c 4c |cting \"|'INSTALL|
|00000540| 41 54 49 4f 4e 27 5c 22 | 20 5c 28 31 37 34 30 20 |ATION'\"| \(1740 |
|00000550| 63 68 61 72 61 63 74 65 | 72 73 5c 29 0a 20 20 73 |characte|rs\). s|
|00000560| 65 64 20 22 73 2f 5e 58 | 2f 2f 22 20 3e 27 49 4e |ed "s/^X|//" >'IN|
|00000570| 53 54 41 4c 4c 41 54 49 | 4f 4e 27 20 3c 3c 27 45 |STALLATI|ON' <<'E|
|00000580| 4e 44 5f 4f 46 5f 46 49 | 4c 45 27 0a 58 0a 58 4d |ND_OF_FI|LE'.X.XM|
|00000590| 61 6b 65 66 69 6c 65 20 | 69 73 20 73 65 74 20 75 |akefile |is set u|
|000005a0| 70 20 66 6f 72 20 53 75 | 6e 4f 53 20 34 2e 31 2e |p for Su|nOS 4.1.|
|000005b0| 20 20 49 66 20 79 6f 75 | 20 77 61 6e 74 20 74 6f | If you| want to|
|000005c0| 20 75 73 65 20 67 63 63 | 2c 20 6d 6f 76 65 20 0a | use gcc|, move .|
|000005d0| 58 74 68 65 20 23 20 63 | 6f 6d 6d 65 6e 74 20 63 |Xthe # c|omment c|
|000005e0| 68 61 72 61 63 74 65 72 | 73 20 69 6e 20 74 68 65 |haracter|s in the|
|000005f0| 20 6d 61 6b 65 66 69 6c | 65 20 61 72 6f 75 6e 64 | makefil|e around|
|00000600| 20 61 70 70 72 6f 70 72 | 69 61 74 65 6c 79 2e 0a | appropr|iately..|
|00000610| 58 0a 58 49 66 20 79 6f | 75 72 20 6d 61 63 68 69 |X.XIf yo|ur machi|
|00000620| 6e 65 20 68 61 73 20 6d | 65 6d 6d 6f 76 65 28 29 |ne has m|emmove()|
|00000630| 20 63 6f 6d 6d 65 6e 74 | 20 6f 75 74 20 74 68 65 | comment| out the|
|00000640| 20 23 64 65 66 69 6e 65 | 20 69 6e 20 73 6f 72 74 | #define| in sort|
|00000650| 69 6e 67 2e 68 0a 58 0a | 58 49 66 20 79 6f 75 20 |ing.h.X.|XIf you |
|00000660| 64 6f 6e 27 74 20 68 61 | 76 65 20 6d 65 6d 63 70 |don't ha|ve memcp|
|00000670| 79 2c 20 63 6f 6d 6d 65 | 6e 74 20 62 61 63 6b 20 |y, comme|nt back |
|00000680| 69 6e 3a 0a 58 20 20 23 | 64 65 66 69 6e 65 20 6d |in:.X #|define m|
|00000690| 65 6d 63 70 79 28 74 6f | 2c 20 66 72 6f 6d 2c 20 |emcpy(to|, from, |
|000006a0| 6e 29 20 62 63 6f 70 79 | 28 66 72 6f 6d 2c 20 74 |n) bcopy|(from, t|
|000006b0| 6f 2c 20 6e 29 0a 58 6f | 72 20 62 65 74 74 65 72 |o, n).Xo|r better|
|000006c0| 20 79 65 74 20 75 70 67 | 72 61 64 65 20 79 6f 75 | yet upg|rade you|
|000006d0| 72 20 4f 53 2e 0a 58 0a | 58 54 79 70 65 20 22 6d |r OS..X.|XType "m|
|000006e0| 61 6b 65 22 20 6f 72 20 | 22 6d 61 6b 65 20 66 6c |ake" or |"make fl|
|000006f0| 6f 67 67 65 72 2e 73 74 | 61 74 69 63 22 0a 58 0a |ogger.st|atic".X.|
|00000700| 58 49 66 20 79 6f 75 20 | 77 61 6e 74 20 74 6f 20 |XIf you |want to |
|00000710| 69 6e 73 74 61 6c 6c 20 | 74 68 65 20 73 6f 72 74 |install |the sort|
|00000720| 20 61 6c 67 6f 72 69 74 | 68 6d 20 6c 69 62 72 61 | algorit|hm libra|
|00000730| 72 79 20 66 6f 72 20 72 | 65 61 6c 0a 58 0a 58 20 |ry for r|eal.X.X |
|00000740| 20 73 75 20 72 6f 6f 74 | 0a 58 20 20 6d 61 6b 65 | su root|.X make|
|00000750| 20 69 6e 73 74 61 6c 6c | 0a 58 0a 58 2d 2d 2d 0a | install|.X.X---.|
|00000760| 58 0a 58 50 6f 74 65 6e | 74 69 61 6c 20 70 6f 72 |X.XPoten|tial por|
|00000770| 74 61 62 69 6c 69 74 79 | 20 70 72 6f 62 6c 65 6d |tability| problem|
|00000780| 73 3a 0a 58 0a 58 53 68 | 61 72 65 64 20 6c 69 62 |s:.X.XSh|ared lib|
|00000790| 72 61 72 69 65 73 20 6d | 69 67 68 74 20 77 6f 72 |raries m|ight wor|
|000007a0| 6b 20 64 69 66 66 65 72 | 65 6e 74 6c 79 2c 20 6f |k differ|ently, o|
|000007b0| 72 20 6e 6f 74 20 61 74 | 20 61 6c 6c 2c 20 6f 6e |r not at| all, on|
|000007c0| 20 79 6f 75 72 0a 58 6d | 61 63 68 69 6e 65 2e 20 | your.Xm|achine. |
|000007d0| 20 45 64 69 74 20 74 68 | 65 20 6d 61 6b 65 66 69 | Edit th|e makefi|
|000007e0| 6c 65 20 61 73 20 6e 65 | 63 65 73 73 61 72 79 2e |le as ne|cessary.|
|000007f0| 0a 58 0a 58 59 6f 75 20 | 6d 69 67 68 74 20 62 65 |.X.XYou |might be|
|00000800| 20 6d 69 73 73 69 6e 67 | 20 6d 61 6c 6c 69 6e 66 | missing| mallinf|
|00000810| 6f 2e 20 20 53 6f 6d 65 | 20 72 65 77 72 69 74 69 |o. Some| rewriti|
|00000820| 6e 67 20 6f 66 20 74 68 | 65 20 63 6f 64 65 20 77 |ng of th|e code w|
|00000830| 69 6c 6c 0a 58 62 65 20 | 69 6e 20 6f 72 64 65 72 |ill.Xbe |in order|
|00000840| 2e 20 20 49 27 6c 6c 20 | 70 75 74 20 73 6f 6d 65 |. I'll |put some|
|00000850| 20 69 66 64 65 66 27 73 | 20 61 72 6f 75 6e 64 20 | ifdef's| around |
|00000860| 74 68 69 73 20 73 6f 6f | 6e 65 72 20 6f 72 20 6c |this soo|ner or l|
|00000870| 61 74 65 72 2e 0a 58 0a | 58 49 66 20 79 6f 75 72 |ater..X.|XIf your|
|00000880| 20 6d 61 63 68 69 6e 65 | 20 64 6f 65 73 6e 27 74 | machine| doesn't|
|00000890| 20 75 73 65 20 61 20 74 | 72 61 64 69 74 69 6f 6e | use a t|radition|
|000008a0| 61 6c 20 73 74 61 63 6b | 2c 20 74 68 65 20 73 74 |al stack|, the st|
|000008b0| 61 63 6b 20 69 6e 66 6f | 72 6d 61 74 69 6f 6e 0a |ack info|rmation.|
|000008c0| 58 77 69 6c 6c 20 62 65 | 20 65 69 74 68 65 72 20 |Xwill be| either |
|000008d0| 70 6c 61 69 6e 20 77 72 | 6f 6e 67 20 6f 72 20 69 |plain wr|ong or i|
|000008e0| 74 20 6d 69 67 68 74 20 | 63 61 75 73 65 20 73 65 |t might |cause se|
|000008f0| 67 6d 65 6e 74 61 74 69 | 6f 6e 20 66 61 75 6c 74 |gmentati|on fault|
|00000900| 73 2e 0a 58 42 75 74 20 | 69 66 20 79 6f 75 20 64 |s..XBut |if you d|
|00000910| 6f 6e 27 74 20 63 61 72 | 65 20 61 62 6f 75 74 20 |on't car|e about |
|00000920| 74 68 65 20 66 6c 6f 67 | 67 65 72 20 72 6f 75 74 |the flog|ger rout|
|00000930| 69 6e 65 2d 2d 20 6e 6f | 20 62 69 67 20 64 65 61 |ine-- no| big dea|
|00000940| 6c 2e 20 20 54 68 65 0a | 58 73 6f 72 74 20 6c 69 |l. The.|Xsort li|
|00000950| 62 72 61 72 79 20 69 74 | 73 65 6c 66 20 73 68 6f |brary it|self sho|
|00000960| 75 6c 64 20 62 65 20 71 | 75 69 74 65 20 70 6f 72 |uld be q|uite por|
|00000970| 74 61 62 6c 65 2c 20 65 | 76 65 6e 20 69 66 20 74 |table, e|ven if t|
|00000980| 68 65 20 74 65 73 74 20 | 72 6f 75 74 69 6e 65 0a |he test |routine.|
|00000990| 58 69 73 6e 27 74 2e 0a | 58 0a 58 54 68 65 20 74 |Xisn't..|X.XThe t|
|000009a0| 79 70 65 64 65 66 73 20 | 66 6f 72 20 63 68 75 6e |ypedefs |for chun|
|000009b0| 6b 34 20 61 6e 64 20 63 | 68 75 6e 6b 38 20 61 72 |k4 and c|hunk8 ar|
|000009c0| 65 20 74 68 6f 72 6f 75 | 67 68 6c 79 20 71 75 65 |e thorou|ghly que|
|000009d0| 73 74 69 6f 6e 61 62 6c | 65 2e 20 20 49 66 0a 58 |stionabl|e. If.X|
|000009e0| 79 6f 75 20 68 61 76 65 | 20 61 20 6d 6f 72 65 20 |you have| a more |
|000009f0| 22 6e 61 74 75 72 61 6c | 22 20 73 69 7a 65 20 6f |"natural|" size o|
|00000a00| 6e 20 79 6f 75 72 20 6d | 61 63 68 69 6e 65 2c 20 |n your m|achine, |
|00000a10| 65 78 70 65 72 69 6d 65 | 6e 74 2e 0a 58 0a 58 49 |experime|nt..X.XI|
|00000a20| 66 20 79 6f 75 20 61 72 | 65 20 70 6f 72 74 69 6e |f you ar|e portin|
|00000a30| 67 20 74 6f 20 61 20 6d | 61 63 68 69 6e 65 20 77 |g to a m|achine w|
|00000a40| 68 69 63 68 20 64 6f 65 | 73 6e 27 74 20 63 61 72 |hich doe|sn't car|
|00000a50| 65 20 61 62 6f 75 74 20 | 61 6c 69 67 6e 6d 65 6e |e about |alignmen|
|00000a60| 74 0a 58 76 65 72 79 20 | 6d 75 63 68 2c 20 79 6f |t.Xvery |much, yo|
|00000a70| 75 20 63 61 6e 20 72 65 | 6d 6f 76 65 20 74 68 65 |u can re|move the|
|00000a80| 20 65 78 74 72 61 20 61 | 6c 69 67 6e 6d 65 6e 74 | extra a|lignment|
|00000a90| 20 74 65 73 74 73 20 66 | 72 6f 6d 20 6d 65 72 67 | tests f|rom merg|
|00000aa0| 65 0a 58 73 6f 72 74 20 | 61 6e 64 20 71 75 69 63 |e.Xsort |and quic|
|00000ab0| 6b 20 73 6f 72 74 20 66 | 6f 72 20 61 20 6d 61 72 |k sort f|or a mar|
|00000ac0| 67 69 6e 61 6c 20 69 6e | 63 72 65 61 73 65 20 69 |ginal in|crease i|
|00000ad0| 6e 20 73 6f 72 74 20 73 | 70 65 65 64 20 75 6e 64 |n sort s|peed und|
|00000ae0| 65 72 20 73 6f 6d 65 20 | 0a 58 63 69 72 63 75 6d |er some |.Xcircum|
|00000af0| 73 74 61 6e 63 65 73 2e | 0a 58 0a 58 6d 65 6d 63 |stances.|.X.Xmemc|
|00000b00| 70 79 28 29 20 69 73 20 | 75 73 65 64 2d 2d 69 66 |py() is |used--if|
|00000b10| 20 79 6f 75 20 68 61 76 | 65 20 61 20 62 65 74 74 | you hav|e a bett|
|00000b20| 65 72 20 62 6c 6f 63 6b | 2d 63 6f 70 79 20 66 75 |er block|-copy fu|
|00000b30| 6e 63 74 69 6f 6e 20 61 | 74 20 79 6f 75 72 0a 58 |nction a|t your.X|
|00000b40| 64 69 73 70 6f 73 61 6c | 2c 20 62 79 20 61 6c 6c |disposal|, by all|
|00000b50| 20 6d 65 61 6e 73 20 70 | 6c 75 67 20 69 74 20 69 | means p|lug it i|
|00000b60| 6e 2e 20 20 57 6f 6e 27 | 74 20 68 65 6c 70 20 6d |n. Won'|t help m|
|00000b70| 75 63 68 20 69 66 20 79 | 6f 75 27 72 65 20 6f 6e |uch if y|ou're on|
|00000b80| 6c 79 0a 58 73 6f 72 74 | 69 6e 67 20 34 2d 62 79 |ly.Xsort|ing 4-by|
|00000b90| 74 65 20 74 68 69 6e 67 | 73 20 6c 69 6b 65 20 69 |te thing|s like i|
|00000ba0| 6e 74 73 20 6f 72 20 70 | 6f 69 6e 74 65 72 73 2c |nts or p|ointers,|
|00000bb0| 20 74 68 6f 75 67 68 2c | 20 27 63 61 75 73 65 0a | though,| 'cause.|
|00000bc0| 58 6d 65 72 67 65 5f 73 | 6f 72 74 20 68 61 73 20 |Xmerge_s|ort has |
|00000bd0| 73 70 65 63 69 61 6c 20 | 63 6f 64 65 20 66 6f 72 |special |code for|
|00000be0| 20 74 68 65 73 65 20 61 | 6e 79 77 61 79 2e 20 20 | these a|nyway. |
|00000bf0| 0a 58 0a 58 73 65 6e 64 | 20 70 61 74 63 68 65 73 |.X.Xsend| patches|
|00000c00| 2c 20 62 75 67 20 66 69 | 78 65 73 2c 20 70 6c 61 |, bug fi|xes, pla|
|00000c10| 6e 65 20 74 69 63 6b 65 | 74 73 20 74 6f 20 70 69 |ne ticke|ts to pi|
|00000c20| 74 74 73 62 75 72 67 68 | 2c 20 65 74 63 20 74 6f |ttsburgh|, etc to|
|00000c30| 20 6d 69 6b 65 79 40 6f | 6e 74 65 6b 2e 63 6f 6d | mikey@o|ntek.com|
|00000c40| 0a 58 0a 58 49 27 6d 20 | 65 73 70 65 63 69 61 6c |.X.XI'm |especial|
|00000c50| 6c 79 20 69 6e 74 65 72 | 65 73 74 65 64 20 69 6e |ly inter|ested in|
|00000c60| 20 70 6f 72 74 61 62 69 | 6c 69 74 79 20 6f 66 20 | portabi|lity of |
|00000c70| 74 68 65 20 6d 65 72 67 | 65 5f 73 6f 72 74 20 72 |the merg|e_sort r|
|00000c80| 6f 75 74 69 6e 65 2e 0a | 58 0a 45 4e 44 5f 4f 46 |outine..|X.END_OF|
|00000c90| 5f 46 49 4c 45 0a 20 20 | 69 66 20 74 65 73 74 20 |_FILE. |if test |
|00000ca0| 31 37 34 30 20 2d 6e 65 | 20 60 77 63 20 2d 63 20 |1740 -ne| `wc -c |
|00000cb0| 3c 27 49 4e 53 54 41 4c | 4c 41 54 49 4f 4e 27 60 |<'INSTAL|LATION'`|
|00000cc0| 3b 20 74 68 65 6e 0a 20 | 20 20 20 65 63 68 6f 20 |; then. | echo |
|00000cd0| 73 68 61 72 3a 20 5c 22 | 27 49 4e 53 54 41 4c 4c |shar: \"|'INSTALL|
|00000ce0| 41 54 49 4f 4e 27 5c 22 | 20 75 6e 70 61 63 6b 65 |ATION'\"| unpacke|
|00000cf0| 64 20 77 69 74 68 20 77 | 72 6f 6e 67 20 73 69 7a |d with w|rong siz|
|00000d00| 65 21 0a 20 20 66 69 0a | 20 20 23 20 65 6e 64 20 |e!. fi.| # end |
|00000d10| 6f 66 20 27 49 4e 53 54 | 41 4c 4c 41 54 49 4f 4e |of 'INST|ALLATION|
|00000d20| 27 0a 66 69 0a 69 66 20 | 74 65 73 74 20 2d 66 20 |'.fi.if |test -f |
|00000d30| 27 4d 61 6b 65 66 69 6c | 65 27 20 2d 61 20 22 24 |'Makefil|e' -a "$|
|00000d40| 7b 31 7d 22 20 21 3d 20 | 22 2d 63 22 20 3b 20 74 |{1}" != |"-c" ; t|
|00000d50| 68 65 6e 20 0a 20 20 65 | 63 68 6f 20 73 68 61 72 |hen . e|cho shar|
|00000d60| 3a 20 57 69 6c 6c 20 6e | 6f 74 20 63 6c 6f 62 62 |: Will n|ot clobb|
|00000d70| 65 72 20 65 78 69 73 74 | 69 6e 67 20 66 69 6c 65 |er exist|ing file|
|00000d80| 20 5c 22 27 4d 61 6b 65 | 66 69 6c 65 27 5c 22 0a | \"'Make|file'\".|
|00000d90| 65 6c 73 65 0a 20 20 65 | 63 68 6f 20 73 68 61 72 |else. e|cho shar|
|00000da0| 3a 20 45 78 74 72 61 63 | 74 69 6e 67 20 5c 22 27 |: Extrac|ting \"'|
|00000db0| 4d 61 6b 65 66 69 6c 65 | 27 5c 22 20 5c 28 31 35 |Makefile|'\" \(15|
|00000dc0| 34 31 20 63 68 61 72 61 | 63 74 65 72 73 5c 29 0a |41 chara|cters\).|
|00000dd0| 20 20 73 65 64 20 22 73 | 2f 5e 58 2f 2f 22 20 3e | sed "s|/^X//" >|
|00000de0| 27 4d 61 6b 65 66 69 6c | 65 27 20 3c 3c 27 45 4e |'Makefil|e' <<'EN|
|00000df0| 44 5f 4f 46 5f 46 49 4c | 45 27 0a 58 0a 58 43 43 |D_OF_FIL|E'.X.XCC|
|00000e00| 20 3d 09 09 63 63 0a 58 | 43 46 4c 41 47 53 20 3d | =..cc.X|CFLAGS =|
|00000e10| 09 2d 4f 34 20 2d 70 69 | 63 0a 58 53 54 41 54 49 |.-O4 -pi|c.XSTATI|
|00000e20| 43 46 4c 41 47 53 20 3d | 09 2d 42 73 74 61 74 69 |CFLAGS =|.-Bstati|
|00000e30| 63 0a 58 0a 58 23 20 43 | 43 20 3d 20 67 63 63 0a |c.X.X# C|C = gcc.|
|00000e40| 58 23 20 43 46 4c 41 47 | 53 20 3d 20 09 2d 66 70 |X# CFLAG|S = .-fp|
|00000e50| 69 63 20 2d 4f 32 20 2d | 61 6e 73 69 20 2d 74 72 |ic -O2 -|ansi -tr|
|00000e60| 61 64 69 74 69 6f 6e 61 | 6c 20 5c 0a 58 23 20 09 |aditiona|l \.X# .|
|00000e70| 09 2d 57 20 2d 57 75 6e | 75 73 65 64 20 2d 57 63 |.-W -Wun|used -Wc|
|00000e80| 6f 6d 6d 65 6e 74 20 2d | 57 74 72 69 67 72 61 70 |omment -|Wtrigrap|
|00000e90| 68 73 20 2d 57 66 6f 72 | 6d 61 74 20 2d 57 75 6e |hs -Wfor|mat -Wun|
|00000ea0| 69 6e 69 74 69 61 6c 69 | 7a 65 64 20 5c 0a 58 23 |initiali|zed \.X#|
|00000eb0| 20 09 09 2d 57 70 61 72 | 65 6e 74 68 65 73 65 73 | ..-Wpar|entheses|
|00000ec0| 20 2d 57 73 68 61 64 6f | 77 20 2d 57 70 6f 69 6e | -Wshado|w -Wpoin|
|00000ed0| 74 65 72 2d 61 72 69 74 | 68 20 2d 57 63 61 73 74 |ter-arit|h -Wcast|
|00000ee0| 2d 71 75 61 6c 20 5c 0a | 58 23 20 09 09 2d 57 63 |-qual \.|X# ..-Wc|
|00000ef0| 6f 6e 76 65 72 73 69 6f | 6e 20 2d 57 73 77 69 74 |onversio|n -Wswit|
|00000f00| 63 68 20 2d 57 69 64 2d | 63 6c 61 73 68 2d 33 32 |ch -Wid-|clash-32|
|00000f10| 0a 58 23 20 53 54 41 54 | 49 43 46 4c 41 47 53 20 |.X# STAT|ICFLAGS |
|00000f20| 3d 09 2d 73 74 61 74 69 | 63 0a 58 0a 58 0a 58 4c |=.-stati|c.X.X.XL|
|00000f30| 44 46 4c 41 47 53 20 3d | 20 09 2d 61 73 73 65 72 |DFLAGS =| .-asser|
|00000f40| 74 20 70 75 72 65 2d 74 | 65 78 74 0a 58 4c 49 4e |t pure-t|ext.XLIN|
|00000f50| 54 46 4c 41 47 53 20 3d | 20 09 2d 61 62 68 75 78 |TFLAGS =| .-abhux|
|00000f60| 7a 0a 58 0a 58 23 20 64 | 6f 6e 27 74 20 69 6e 73 |z.X.X# d|on't ins|
|00000f70| 65 72 74 20 61 20 6c 69 | 6e 65 20 62 72 65 61 6b |ert a li|ne break|
|00000f80| 20 61 66 74 65 72 20 74 | 68 65 20 2d 64 0a 58 53 | after t|he -d.XS|
|00000f90| 48 41 52 46 4c 41 47 53 | 20 3d 09 2d 76 20 2d 6c |HARFLAGS| =.-v -l|
|00000fa0| 34 30 20 2d 4d 20 2d 64 | 5f 5f 4b 52 49 4c 4c 5f |40 -M -d|__KRILL_|
|00000fb0| 41 52 45 5f 59 55 4d 4d | 59 5f 41 4e 44 5f 43 52 |ARE_YUMM|Y_AND_CR|
|00000fc0| 55 4e 43 48 59 0a 58 0a | 58 56 45 52 53 49 4f 4e |UNCHY.X.|XVERSION|
|00000fd0| 20 3d 09 30 2e 30 0a 58 | 53 48 45 4c 4c 20 3d 09 | =.0.0.X|SHELL =.|
|00000fe0| 09 2f 62 69 6e 2f 73 68 | 0a 58 0a 58 4f 42 4a 53 |./bin/sh|.X.XOBJS|
|00000ff0| 20 3d 20 09 6d 65 72 67 | 65 5f 73 6f 72 74 2e 6f | = .merg|e_sort.o|
|00001000| 20 5c 0a 58 09 71 75 69 | 63 6b 5f 73 6f 72 74 2e | \.X.qui|ck_sort.|
|00001010| 6f 20 5c 0a 58 09 68 65 | 61 70 5f 73 6f 72 74 2e |o \.X.he|ap_sort.|
|00001020| 6f 20 5c 0a 58 09 73 68 | 65 6c 6c 5f 73 6f 72 74 |o \.X.sh|ell_sort|
|00001030| 2e 6f 20 5c 0a 58 09 62 | 75 62 62 6c 65 5f 73 6f |.o \.X.b|ubble_so|
|00001040| 72 74 2e 6f 20 5c 0a 58 | 09 62 6f 67 6f 5f 73 6f |rt.o \.X|.bogo_so|
|00001050| 72 74 2e 6f 20 5c 0a 58 | 09 69 6e 73 65 72 74 5f |rt.o \.X|.insert_|
|00001060| 73 6f 72 74 2e 6f 0a 58 | 0a 58 66 6c 6f 67 67 65 |sort.o.X|.Xflogge|
|00001070| 72 3a 20 66 6c 6f 67 67 | 65 72 2e 6f 20 6c 69 62 |r: flogg|er.o lib|
|00001080| 73 6f 72 74 2e 73 6f 2e | 24 28 56 45 52 53 49 4f |sort.so.|$(VERSIO|
|00001090| 4e 29 0a 58 09 24 28 43 | 43 29 20 24 28 43 46 4c |N).X.$(C|C) $(CFL|
|000010a0| 41 47 53 29 20 2d 6f 20 | 66 6c 6f 67 67 65 72 20 |AGS) -o |flogger |
|000010b0| 66 6c 6f 67 67 65 72 2e | 6f 20 2d 4c 2e 20 2d 6c |flogger.|o -L. -l|
|000010c0| 73 6f 72 74 0a 58 0a 58 | 66 6c 6f 67 67 65 72 2e |sort.X.X|flogger.|
|000010d0| 73 74 61 74 69 63 3a 20 | 66 6c 6f 67 67 65 72 2e |static: |flogger.|
|000010e0| 6f 20 6c 69 62 73 6f 72 | 74 2e 61 0a 58 09 24 28 |o libsor|t.a.X.$(|
|000010f0| 43 43 29 20 24 28 43 46 | 4c 41 47 53 29 20 24 28 |CC) $(CF|LAGS) $(|
|00001100| 53 54 41 54 49 43 46 4c | 41 47 53 29 20 2d 6f 20 |STATICFL|AGS) -o |
|00001110| 66 6c 6f 67 67 65 72 2e | 73 74 61 74 69 63 20 66 |flogger.|static f|
|00001120| 6c 6f 67 67 65 72 2e 6f | 20 2d 4c 2e 20 2d 6c 73 |logger.o| -L. -ls|
|00001130| 6f 72 74 0a 58 0a 58 6c | 69 62 73 6f 72 74 2e 61 |ort.X.Xl|ibsort.a|
|00001140| 3a 20 24 28 4f 42 4a 53 | 29 0a 58 09 61 72 20 72 |: $(OBJS|).X.ar r|
|00001150| 75 20 6c 69 62 73 6f 72 | 74 2e 61 20 24 28 4f 42 |u libsor|t.a $(OB|
|00001160| 4a 53 29 0a 58 09 72 61 | 6e 6c 69 62 20 6c 69 62 |JS).X.ra|nlib lib|
|00001170| 73 6f 72 74 2e 61 0a 58 | 0a 58 6c 69 62 73 6f 72 |sort.a.X|.Xlibsor|
|00001180| 74 2e 73 6f 2e 24 28 56 | 45 52 53 49 4f 4e 29 3a |t.so.$(V|ERSION):|
|00001190| 20 24 28 4f 42 4a 53 29 | 0a 58 09 6c 64 20 24 28 | $(OBJS)|.X.ld $(|
|000011a0| 4c 44 46 4c 41 47 53 29 | 20 24 28 4f 42 4a 53 29 |LDFLAGS)| $(OBJS)|
|000011b0| 20 2d 6f 20 6c 69 62 73 | 6f 72 74 2e 73 6f 2e 24 | -o libs|ort.so.$|
|000011c0| 28 56 45 52 53 49 4f 4e | 29 0a 58 0a 58 24 28 4f |(VERSION|).X.X$(O|
|000011d0| 42 4a 53 29 3a 20 73 6f | 72 74 69 6e 67 2e 68 0a |BJS): so|rting.h.|
|000011e0| 58 0a 58 69 6e 73 74 61 | 6c 6c 3a 20 6c 69 62 73 |X.Xinsta|ll: libs|
|000011f0| 6f 72 74 2e 73 6f 2e 24 | 28 56 45 52 53 49 4f 4e |ort.so.$|(VERSION|
|00001200| 29 20 6c 69 62 73 6f 72 | 74 2e 61 0a 58 09 63 70 |) libsor|t.a.X.cp|
|00001210| 20 6c 69 62 73 6f 72 74 | 2e 61 20 2f 75 73 72 2f | libsort|.a /usr/|
|00001220| 6c 69 62 0a 58 09 63 68 | 6d 6f 64 20 36 34 34 20 |lib.X.ch|mod 644 |
|00001230| 2f 75 73 72 2f 6c 69 62 | 2f 6c 69 62 73 6f 72 74 |/usr/lib|/libsort|
|00001240| 2e 61 0a 58 09 63 70 20 | 6c 69 62 73 6f 72 74 2e |.a.X.cp |libsort.|
|00001250| 73 6f 2e 24 28 56 45 52 | 53 49 4f 4e 29 20 2f 75 |so.$(VER|SION) /u|
|00001260| 73 72 2f 6c 69 62 0a 58 | 09 63 68 6d 6f 64 20 37 |sr/lib.X|.chmod 7|
|00001270| 35 35 20 2f 75 73 72 2f | 6c 69 62 2f 6c 69 62 73 |55 /usr/|lib/libs|
|00001280| 6f 72 74 2e 73 6f 2e 24 | 28 56 45 52 53 49 4f 4e |ort.so.$|(VERSION|
|00001290| 29 0a 58 09 2f 75 73 72 | 2f 65 74 63 2f 6c 64 63 |).X./usr|/etc/ldc|
|000012a0| 6f 6e 66 69 67 0a 58 0a | 58 6c 69 6e 74 3a 09 6c |onfig.X.|Xlint:.l|
|000012b0| 69 6e 74 2e 6f 75 74 0a | 58 0a 58 6c 69 6e 74 2e |int.out.|X.Xlint.|
|000012c0| 6f 75 74 3a 20 2a 2e 63 | 20 73 6f 72 74 69 6e 67 |out: *.c| sorting|
|000012d0| 2e 68 0a 58 09 6c 69 6e | 74 20 24 28 4c 49 4e 54 |.h.X.lin|t $(LINT|
|000012e0| 46 4c 41 47 53 29 20 2a | 2e 63 20 3e 20 6c 69 6e |FLAGS) *|.c > lin|
|000012f0| 74 2e 6f 75 74 20 32 3e | 26 31 0a 58 0a 58 63 6c |t.out 2>|&1.X.Xcl|
|00001300| 65 61 6e 3a 0a 58 09 2d | 72 6d 20 2d 66 20 63 6f |ean:.X.-|rm -f co|
|00001310| 72 65 20 73 68 61 72 30 | 3f 20 24 28 4f 42 4a 53 |re shar0|? $(OBJS|
|00001320| 29 20 5c 0a 58 09 6c 69 | 62 73 6f 72 74 2e 73 6f |) \.X.li|bsort.so|
|00001330| 2e 24 28 56 45 52 53 49 | 4f 4e 29 20 6c 69 62 73 |.$(VERSI|ON) libs|
|00001340| 6f 72 74 2e 61 20 66 6c | 6f 67 67 65 72 2e 6f 20 |ort.a fl|ogger.o |
|00001350| 5c 0a 58 09 66 6c 6f 67 | 67 65 72 20 66 6c 6f 67 |\.X.flog|ger flog|
|00001360| 67 65 72 2e 73 74 61 74 | 69 63 20 6c 69 6e 74 2e |ger.stat|ic lint.|
|00001370| 6f 75 74 0a 58 0a 58 73 | 68 61 72 3a 09 0a 58 09 |out.X.Xs|har:..X.|
|00001380| 73 68 61 72 20 24 28 53 | 48 41 52 46 4c 41 47 53 |shar $(S|HARFLAGS|
|00001390| 29 20 2d 6f 20 73 68 61 | 72 20 5c 0a 58 09 52 45 |) -o sha|r \.X.RE|
|000013a0| 41 44 4d 45 20 49 4e 53 | 54 41 4c 4c 41 54 49 4f |ADME INS|TALLATIO|
|000013b0| 4e 20 54 4f 44 4f 20 4f | 50 54 49 4d 49 5a 49 4e |N TODO O|PTIMIZIN|
|000013c0| 47 20 4d 61 6b 65 66 69 | 6c 65 20 62 75 62 62 6c |G Makefi|le bubbl|
|000013d0| 65 5f 73 6f 72 74 2e 63 | 20 5c 0a 58 09 68 65 61 |e_sort.c| \.X.hea|
|000013e0| 70 5f 73 6f 72 74 2e 63 | 20 6d 65 72 67 65 5f 73 |p_sort.c| merge_s|
|000013f0| 6f 72 74 2e 63 20 71 75 | 69 63 6b 5f 73 6f 72 74 |ort.c qu|ick_sort|
|00001400| 2e 63 20 73 68 65 6c 6c | 5f 73 6f 72 74 2e 63 20 |.c shell|_sort.c |
|00001410| 69 6e 73 65 72 74 5f 73 | 6f 72 74 2e 63 20 5c 0a |insert_s|ort.c \.|
|00001420| 58 09 73 6f 72 74 69 6e | 67 2e 68 20 66 6c 6f 67 |X.sortin|g.h flog|
|00001430| 67 65 72 2e 63 20 62 6f | 67 6f 5f 73 6f 72 74 2e |ger.c bo|go_sort.|
|00001440| 63 0a 58 0a 45 4e 44 5f | 4f 46 5f 46 49 4c 45 0a |c.X.END_|OF_FILE.|
|00001450| 20 20 69 66 20 74 65 73 | 74 20 31 35 34 31 20 2d | if tes|t 1541 -|
|00001460| 6e 65 20 60 77 63 20 2d | 63 20 3c 27 4d 61 6b 65 |ne `wc -|c <'Make|
|00001470| 66 69 6c 65 27 60 3b 20 | 74 68 65 6e 0a 20 20 20 |file'`; |then. |
|00001480| 20 65 63 68 6f 20 73 68 | 61 72 3a 20 5c 22 27 4d | echo sh|ar: \"'M|
|00001490| 61 6b 65 66 69 6c 65 27 | 5c 22 20 75 6e 70 61 63 |akefile'|\" unpac|
|000014a0| 6b 65 64 20 77 69 74 68 | 20 77 72 6f 6e 67 20 73 |ked with| wrong s|
|000014b0| 69 7a 65 21 0a 20 20 66 | 69 0a 20 20 23 20 65 6e |ize!. f|i. # en|
|000014c0| 64 20 6f 66 20 27 4d 61 | 6b 65 66 69 6c 65 27 0a |d of 'Ma|kefile'.|
|000014d0| 66 69 0a 69 66 20 74 65 | 73 74 20 2d 66 20 27 62 |fi.if te|st -f 'b|
|000014e0| 6f 67 6f 5f 73 6f 72 74 | 2e 63 27 20 2d 61 20 22 |ogo_sort|.c' -a "|
|000014f0| 24 7b 31 7d 22 20 21 3d | 20 22 2d 63 22 20 3b 20 |${1}" !=| "-c" ; |
|00001500| 74 68 65 6e 20 0a 20 20 | 65 63 68 6f 20 73 68 61 |then . |echo sha|
|00001510| 72 3a 20 57 69 6c 6c 20 | 6e 6f 74 20 63 6c 6f 62 |r: Will |not clob|
|00001520| 62 65 72 20 65 78 69 73 | 74 69 6e 67 20 66 69 6c |ber exis|ting fil|
|00001530| 65 20 5c 22 27 62 6f 67 | 6f 5f 73 6f 72 74 2e 63 |e \"'bog|o_sort.c|
|00001540| 27 5c 22 0a 65 6c 73 65 | 0a 20 20 65 63 68 6f 20 |'\".else|. echo |
|00001550| 73 68 61 72 3a 20 45 78 | 74 72 61 63 74 69 6e 67 |shar: Ex|tracting|
|00001560| 20 5c 22 27 62 6f 67 6f | 5f 73 6f 72 74 2e 63 27 | \"'bogo|_sort.c'|
|00001570| 5c 22 20 5c 28 34 32 31 | 31 20 63 68 61 72 61 63 |\" \(421|1 charac|
|00001580| 74 65 72 73 5c 29 0a 20 | 20 73 65 64 20 22 73 2f |ters\). | sed "s/|
|00001590| 5e 58 2f 2f 22 20 3e 27 | 62 6f 67 6f 5f 73 6f 72 |^X//" >'|bogo_sor|
|000015a0| 74 2e 63 27 20 3c 3c 27 | 45 4e 44 5f 4f 46 5f 46 |t.c' <<'|END_OF_F|
|000015b0| 49 4c 45 27 0a 58 0a 58 | 23 75 6e 64 65 66 20 54 |ILE'.X.X|#undef T|
|000015c0| 45 53 54 0a 58 23 64 65 | 66 69 6e 65 20 45 58 49 |EST.X#de|fine EXI|
|000015d0| 54 5f 53 55 43 43 45 53 | 53 20 30 0a 58 23 64 65 |T_SUCCES|S 0.X#de|
|000015e0| 66 69 6e 65 20 45 58 49 | 54 5f 46 41 49 4c 55 52 |fine EXI|T_FAILUR|
|000015f0| 45 20 31 0a 58 23 64 65 | 66 69 6e 65 20 52 41 4e |E 1.X#de|fine RAN|
|00001600| 44 5f 4d 41 58 20 33 32 | 37 36 37 0a 58 0a 58 2f |D_MAX 32|767.X.X/|
|00001610| 2a 0a 58 0a 58 49 6e 20 | 61 6c 74 2e 66 6f 6c 6b |*.X.XIn |alt.folk|
|00001620| 6c 6f 72 65 2e 63 6f 6d | 70 75 74 65 72 73 2c 20 |lore.com|puters, |
|00001630| 74 68 65 72 65 20 68 61 | 73 20 62 65 65 6e 20 61 |there ha|s been a|
|00001640| 20 64 69 73 63 75 73 73 | 69 6f 6e 20 6f 66 20 74 | discuss|ion of t|
|00001650| 68 65 20 77 6f 72 73 74 | 0a 58 70 6f 73 73 69 62 |he worst|.Xpossib|
|00001660| 6c 65 20 73 6f 72 74 69 | 6e 67 20 61 6c 67 6f 72 |le sorti|ng algor|
|00001670| 69 74 68 6d 2c 20 77 68 | 69 63 68 20 68 61 73 20 |ithm, wh|ich has |
|00001680| 62 65 65 6e 20 63 61 6c | 6c 65 64 20 22 62 6f 67 |been cal|led "bog|
|00001690| 6f 73 6f 72 74 22 2e 0a | 58 0a 58 4d 79 20 69 6e |osort"..|X.XMy in|
|000016a0| 74 65 72 70 72 65 74 61 | 74 69 6f 6e 20 6f 66 20 |terpreta|tion of |
|000016b0| 74 68 65 20 61 6c 67 6f | 72 69 74 68 6d 20 69 73 |the algo|rithm is|
|000016c0| 20 74 68 69 73 3a 20 45 | 78 63 68 61 6e 67 65 20 | this: E|xchange |
|000016d0| 74 77 6f 20 72 61 6e 64 | 6f 6d 6c 79 0a 58 63 68 |two rand|omly.Xch|
|000016e0| 6f 73 65 6e 20 65 6c 65 | 6d 65 6e 74 73 20 6f 66 |osen ele|ments of|
|000016f0| 20 74 68 65 20 61 72 72 | 61 79 20 74 6f 20 62 65 | the arr|ay to be|
|00001700| 20 73 6f 72 74 65 64 2e | 20 20 43 68 65 63 6b 20 | sorted.| Check |
|00001710| 74 6f 20 73 65 65 20 69 | 66 20 74 68 65 20 61 72 |to see i|f the ar|
|00001720| 72 61 79 0a 58 69 73 20 | 69 6e 20 6f 72 64 65 72 |ray.Xis |in order|
|00001730| 2e 20 20 49 74 65 72 61 | 74 65 20 75 6e 74 69 6c |. Itera|te until|
|00001740| 20 64 6f 6e 65 2e 0a 58 | 0a 58 46 72 6f 6d 20 77 | done..X|.XFrom w|
|00001750| 68 61 74 20 49 27 76 65 | 20 72 65 61 64 2c 20 74 |hat I've| read, t|
|00001760| 68 65 6f 72 65 74 69 63 | 61 6c 20 61 6e 61 6c 79 |heoretic|al analy|
|00001770| 73 69 73 20 6f 66 20 74 | 68 69 73 20 61 6c 67 6f |sis of t|his algo|
|00001780| 72 69 74 68 6d 20 67 69 | 76 65 73 20 69 74 20 61 |rithm gi|ves it a|
|00001790| 0a 58 70 65 72 66 6f 72 | 6d 61 6e 63 65 20 6f 66 |.Xperfor|mance of|
|000017a0| 20 4f 28 6e 21 29 2c 20 | 77 68 69 63 68 20 6d 65 | O(n!), |which me|
|000017b0| 61 6e 73 20 74 68 61 74 | 20 74 68 65 20 74 69 6d |ans that| the tim|
|000017c0| 65 20 74 6f 20 73 6f 72 | 74 20 69 73 0a 58 70 72 |e to sor|t is.Xpr|
|000017d0| 6f 70 6f 72 74 69 6f 6e | 61 6c 20 74 6f 20 74 68 |oportion|al to th|
|000017e0| 65 20 66 61 63 74 6f 72 | 69 61 6c 20 6f 66 20 74 |e factor|ial of t|
|000017f0| 68 65 20 6e 75 6d 62 65 | 72 20 6f 66 20 65 6c 65 |he numbe|r of ele|
|00001800| 6d 65 6e 74 73 2e 20 20 | 41 6e 64 20 73 69 6e 63 |ments. |And sinc|
|00001810| 65 0a 58 74 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |e.Xthe a|lgorithm|
|00001820| 20 69 73 20 72 61 6e 64 | 6f 6d 20 69 6e 20 6e 61 | is rand|om in na|
|00001830| 74 75 72 65 2c 20 69 74 | 20 63 6f 75 6c 64 20 72 |ture, it| could r|
|00001840| 61 6e 67 65 20 66 72 6f | 6d 20 69 6e 73 74 61 6e |ange fro|m instan|
|00001850| 74 61 6e 65 6f 75 73 0a | 58 28 6f 6e 6c 79 20 74 |taneous.|X(only t|
|00001860| 77 6f 20 65 6e 74 72 69 | 65 73 20 6f 75 74 20 6f |wo entri|es out o|
|00001870| 66 20 6f 72 64 65 72 2c | 20 61 6e 64 20 69 74 20 |f order,| and it |
|00001880| 68 61 70 70 65 6e 73 20 | 74 6f 20 65 78 63 68 61 |happens |to excha|
|00001890| 6e 67 65 20 74 68 65 6d | 20 66 69 72 73 74 29 0a |nge them| first).|
|000018a0| 58 74 6f 20 74 6f 20 69 | 6e 66 69 6e 69 74 65 20 |Xto to i|nfinite |
|000018b0| 28 69 74 20 6d 69 67 68 | 74 20 6e 65 76 65 72 20 |(it migh|t never |
|000018c0| 73 75 63 63 65 65 64 29 | 2e 0a 58 0a 58 53 6f 2c |succeed)|..X.XSo,|
|000018d0| 20 66 6f 72 20 6b 69 63 | 6b 73 20 49 20 63 6f 64 | for kic|ks I cod|
|000018e0| 65 64 20 75 70 20 61 20 | 62 6f 67 6f 73 6f 72 74 |ed up a |bogosort|
|000018f0| 20 72 6f 75 74 69 6e 65 | 2e 0a 58 0a 58 49 6e 20 | routine|..X.XIn |
|00001900| 6d 79 20 74 65 73 74 69 | 6e 67 2c 20 49 20 64 69 |my testi|ng, I di|
|00001910| 73 63 6f 76 65 72 65 64 | 20 74 68 61 74 20 74 68 |scovered| that th|
|00001920| 65 20 6d 65 61 6e 20 74 | 69 6d 65 20 74 6f 20 73 |e mean t|ime to s|
|00001930| 6f 72 74 20 61 6e 20 61 | 72 72 61 79 20 6f 66 20 |ort an a|rray of |
|00001940| 74 65 6e 0a 58 69 6e 74 | 65 67 65 72 73 20 77 61 |ten.Xint|egers wa|
|00001950| 73 20 37 35 20 73 65 63 | 6f 6e 64 73 20 28 32 35 |s 75 sec|onds (25|
|00001960| 4d 48 7a 20 34 38 36 2c | 20 55 6e 69 78 2c 20 67 |MHz 486,| Unix, g|
|00001970| 63 63 20 32 2e 31 2c 20 | 22 6f 70 74 69 6d 69 7a |cc 2.1, |"optimiz|
|00001980| 65 64 22 29 2e 0a 58 0a | 58 45 78 74 72 61 70 6f |ed")..X.|XExtrapo|
|00001990| 6c 61 74 69 6e 67 20 66 | 72 6f 6d 20 74 68 69 73 |lating f|rom this|
|000019a0| 2c 20 61 73 73 75 6d 69 | 6e 67 20 4f 28 6e 21 29 |, assumi|ng O(n!)|
|000019b0| 2c 20 67 69 76 65 73 20 | 33 31 32 20 64 61 79 73 |, gives |312 days|
|000019c0| 20 74 6f 20 73 6f 72 74 | 20 31 35 0a 58 69 6e 74 | to sort| 15.Xint|
|000019d0| 65 67 65 72 73 20 61 6e | 64 20 31 2c 35 39 33 2c |egers an|d 1,593,|
|000019e0| 33 37 38 20 79 65 61 72 | 73 20 74 6f 20 73 6f 72 |378 year|s to sor|
|000019f0| 74 20 32 30 20 69 6e 74 | 65 67 65 72 73 2e 20 20 |t 20 int|egers. |
|00001a00| 53 6f 6d 65 6f 6e 65 20 | 77 69 74 68 20 61 20 6d |Someone |with a m|
|00001a10| 75 63 68 0a 58 66 61 73 | 74 65 72 20 6d 61 63 68 |uch.Xfas|ter mach|
|00001a20| 69 6e 65 20 74 68 61 6e | 20 6d 69 6e 65 20 77 69 |ine than| mine wi|
|00001a30| 6c 6c 20 68 61 76 65 20 | 74 6f 20 76 65 72 69 66 |ll have |to verif|
|00001a40| 79 20 74 68 65 73 65 20 | 66 69 67 75 72 65 73 2e |y these |figures.|
|00001a50| 0a 58 0a 58 2d 2d 20 0a | 58 52 69 63 68 61 72 64 |.X.X-- .|XRichard|
|00001a60| 20 4b 72 65 68 62 69 65 | 6c 20 20 20 20 20 20 20 | Krehbie|l |
|00001a70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001a80| 20 20 20 20 20 20 20 20 | 20 20 72 69 63 68 6b 40 | | richk@|
|00001a90| 67 72 65 62 79 6e 2e 63 | 6f 6d 0a 58 4f 53 2f 32 |grebyn.c|om.XOS/2|
|00001aa0| 20 32 2e 30 20 77 69 6c | 6c 20 64 6f 20 66 6f 72 | 2.0 wil|l do for|
|00001ab0| 20 6d 65 20 75 6e 74 69 | 6c 20 41 6d 69 67 61 44 | me unti|l AmigaD|
|00001ac0| 4f 53 20 66 6f 72 20 74 | 68 65 20 33 38 36 20 63 |OS for t|he 386 c|
|00001ad0| 6f 6d 65 73 20 61 6c 6f | 6e 67 2e 2e 2e 0a 58 0a |omes alo|ng....X.|
|00001ae0| 58 0a 58 3d 3d 3d 3d 3d | 20 63 75 74 20 68 65 72 |X.X=====| cut her|
|00001af0| 65 20 3d 3d 3d 3d 3d 3d | 20 62 6f 67 6f 73 6f 72 |e ======| bogosor|
|00001b00| 74 2e 63 20 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |t.c ====|========|
|00001b10| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00001b20| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 0a 58 0a 58 2a 2f 0a |========|=.X.X*/.|
|00001b30| 58 0a 58 23 69 6e 63 6c | 75 64 65 20 3c 73 74 64 |X.X#incl|ude <std|
|00001b40| 69 6f 2e 68 3e 0a 58 23 | 69 6e 63 6c 75 64 65 20 |io.h>.X#|include |
|00001b50| 3c 73 74 64 6c 69 62 2e | 68 3e 0a 58 23 69 6e 63 |<stdlib.|h>.X#inc|
|00001b60| 6c 75 64 65 20 3c 74 69 | 6d 65 2e 68 3e 0a 58 23 |lude <ti|me.h>.X#|
|00001b70| 69 6e 63 6c 75 64 65 20 | 3c 61 73 73 65 72 74 2e |include |<assert.|
|00001b80| 68 3e 0a 58 0a 58 23 64 | 65 66 69 6e 65 20 54 52 |h>.X.X#d|efine TR|
|00001b90| 55 45 20 31 0a 58 23 64 | 65 66 69 6e 65 20 46 41 |UE 1.X#d|efine FA|
|00001ba0| 4c 53 45 20 30 0a 58 0a | 58 23 69 66 20 30 0a 58 |LSE 0.X.|X#if 0.X|
|00001bb0| 23 64 65 66 69 6e 65 20 | 72 61 6e 67 65 5f 72 61 |#define |range_ra|
|00001bc0| 6e 64 28 72 61 6e 67 65 | 29 20 28 28 6c 6f 6e 67 |nd(range|) ((long|
|00001bd0| 29 72 61 6e 64 28 29 20 | 2a 20 28 6c 6f 6e 67 29 |)rand() |* (long)|
|00001be0| 72 61 6e 67 65 20 2f 20 | 28 52 41 4e 44 5f 4d 41 |range / |(RAND_MA|
|00001bf0| 58 20 2b 20 31 29 29 0a | 58 0a 58 23 69 66 20 21 |X + 1)).|X.X#if !|
|00001c00| 20 64 65 66 69 6e 65 64 | 28 72 61 6e 67 65 5f 72 | defined|(range_r|
|00001c10| 61 6e 64 29 0a 58 69 6e | 74 20 72 61 6e 67 65 5f |and).Xin|t range_|
|00001c20| 72 61 6e 64 28 72 61 6e | 67 65 29 20 69 6e 74 20 |rand(ran|ge) int |
|00001c30| 72 61 6e 67 65 3b 0a 58 | 7b 0a 58 09 72 65 74 75 |range;.X|{.X.retu|
|00001c40| 72 6e 20 28 6c 6f 6e 67 | 29 72 61 6e 64 28 29 20 |rn (long|)rand() |
|00001c50| 2a 20 28 6c 6f 6e 67 29 | 72 61 6e 67 65 20 2f 20 |* (long)|range / |
|00001c60| 28 52 41 4e 44 5f 4d 41 | 58 20 2b 20 31 29 3b 0a |(RAND_MA|X + 1);.|
|00001c70| 58 7d 0a 58 23 65 6e 64 | 69 66 0a 58 0a 58 23 65 |X}.X#end|if.X.X#e|
|00001c80| 6e 64 69 66 0a 58 0a 58 | 2f 2a 20 62 6f 67 6f 20 |ndif.X.X|/* bogo |
|00001c90| 73 6f 72 74 20 69 73 20 | 73 65 6e 73 69 74 69 76 |sort is |sensitiv|
|00001ca0| 65 20 74 6f 20 72 61 6e | 64 28 29 27 73 20 72 65 |e to ran|d()'s re|
|00001cb0| 70 65 61 74 69 6e 67 2d | 6c 6f 77 65 72 2d 64 69 |peating-|lower-di|
|00001cc0| 67 69 74 73 20 66 65 61 | 74 75 72 65 20 0a 58 20 |gits fea|ture .X |
|00001cd0| 20 20 70 6c 75 73 20 74 | 68 65 20 61 62 6f 76 65 | plus t|he above|
|00001ce0| 20 6d 61 63 72 6f 20 61 | 6e 64 20 66 75 6e 63 74 | macro a|nd funct|
|00001cf0| 69 6f 6e 20 67 61 76 65 | 20 6d 65 20 64 69 66 66 |ion gave| me diff|
|00001d00| 65 72 65 6e 74 20 72 65 | 73 75 6c 74 73 20 77 69 |erent re|sults wi|
|00001d10| 74 68 0a 58 20 20 20 61 | 6e 64 20 77 69 74 68 6f |th.X a|nd witho|
|00001d20| 75 74 20 2d 4f 2c 20 73 | 6f 20 49 20 72 65 70 6c |ut -O, s|o I repl|
|00001d30| 61 63 65 64 20 74 68 65 | 6d 20 77 69 74 68 20 74 |aced the|m with t|
|00001d40| 68 69 73 20 73 6c 6f 77 | 20 62 75 74 20 73 65 72 |his slow| but ser|
|00001d50| 76 69 63 65 61 62 6c 65 | 0a 58 20 20 20 66 75 6e |viceable|.X fun|
|00001d60| 63 74 69 6f 6e 2e 20 2a | 2f 0a 58 0a 58 69 6e 74 |ction. *|/.X.Xint|
|00001d70| 20 72 61 6e 67 65 5f 72 | 61 6e 64 28 72 61 6e 67 | range_r|and(rang|
|00001d80| 65 29 20 0a 58 20 20 69 | 6e 74 20 72 61 6e 67 65 |e) .X i|nt range|
|00001d90| 3b 0a 58 7b 0a 58 20 20 | 69 6e 74 20 72 65 73 75 |;.X{.X |int resu|
|00001da0| 6c 74 3b 0a 58 20 20 65 | 78 74 65 72 6e 20 6c 6f |lt;.X e|xtern lo|
|00001db0| 6e 67 20 72 61 6e 64 6f | 6d 28 29 3b 0a 58 0a 58 |ng rando|m();.X.X|
|00001dc0| 20 20 64 6f 20 7b 20 0a | 58 20 20 20 20 72 65 73 | do { .|X res|
|00001dd0| 75 6c 74 20 3d 20 28 69 | 6e 74 29 20 72 61 6e 64 |ult = (i|nt) rand|
|00001de0| 6f 6d 28 29 3b 20 0a 58 | 20 20 7d 20 0a 58 20 20 |om(); .X| } .X |
|00001df0| 77 68 69 6c 65 20 28 72 | 65 73 75 6c 74 20 3c 20 |while (r|esult < |
|00001e00| 30 29 3b 0a 58 20 20 0a | 58 20 20 72 65 73 75 6c |0);.X .|X resul|
|00001e10| 74 20 3d 20 72 65 73 75 | 6c 74 20 25 20 72 61 6e |t = resu|lt % ran|
|00001e20| 67 65 3b 0a 58 0a 58 20 | 20 72 65 74 75 72 6e 20 |ge;.X.X | return |
|00001e30| 72 65 73 75 6c 74 3b 0a | 58 7d 0a 58 0a 58 0a 58 |result;.|X}.X.X.X|
|00001e40| 76 6f 69 64 20 73 77 61 | 70 5f 65 6c 65 6d 28 65 |void swa|p_elem(e|
|00001e50| 6c 65 6d 31 2c 20 65 6c | 65 6d 32 2c 20 65 6c 65 |lem1, el|em2, ele|
|00001e60| 6d 5f 73 69 7a 65 29 20 | 0a 58 09 09 09 20 20 20 |m_size) |.X... |
|00001e70| 72 65 67 69 73 74 65 72 | 20 63 68 61 72 20 2a 65 |register| char *e|
|00001e80| 6c 65 6d 31 3b 0a 58 09 | 09 09 20 20 20 72 65 67 |lem1;.X.|.. reg|
|00001e90| 69 73 74 65 72 20 63 68 | 61 72 20 2a 65 6c 65 6d |ister ch|ar *elem|
|00001ea0| 32 3b 0a 58 09 09 09 20 | 20 20 72 65 67 69 73 74 |2;.X... | regist|
|00001eb0| 65 72 20 73 69 7a 65 5f | 74 20 65 6c 65 6d 5f 73 |er size_|t elem_s|
|00001ec0| 69 7a 65 3b 0a 58 0a 58 | 7b 0a 58 09 2f 2a 2a 2a |ize;.X.X|{.X./***|
|00001ed0| 0a 58 09 69 6e 74 20 74 | 65 6d 70 3b 0a 58 0a 58 |.X.int t|emp;.X.X|
|00001ee0| 09 74 65 6d 70 20 3d 20 | 2a 28 69 6e 74 2a 29 20 |.temp = |*(int*) |
|00001ef0| 65 6c 65 6d 31 3b 0a 58 | 09 2a 28 69 6e 74 2a 29 |elem1;.X|.*(int*)|
|00001f00| 20 65 6c 65 6d 31 20 3d | 20 2a 28 69 6e 74 2a 29 | elem1 =| *(int*)|
|00001f10| 20 65 6c 65 6d 32 3b 0a | 58 09 2a 28 69 6e 74 2a | elem2;.|X.*(int*|
|00001f20| 29 20 65 6c 65 6d 32 20 | 3d 20 74 65 6d 70 3b 0a |) elem2 |= temp;.|
|00001f30| 58 09 2a 2a 2a 2f 0a 58 | 0a 58 09 77 68 69 6c 65 |X.***/.X|.X.while|
|00001f40| 28 65 6c 65 6d 5f 73 69 | 7a 65 2d 2d 20 3e 20 30 |(elem_si|ze-- > 0|
|00001f50| 29 0a 58 09 7b 0a 58 09 | 09 63 68 61 72 20 74 65 |).X.{.X.|.char te|
|00001f60| 6d 70 3b 0a 58 09 09 74 | 65 6d 70 20 3d 20 2a 65 |mp;.X..t|emp = *e|
|00001f70| 6c 65 6d 31 3b 0a 58 09 | 09 2a 65 6c 65 6d 31 2b |lem1;.X.|.*elem1+|
|00001f80| 2b 20 3d 20 2a 65 6c 65 | 6d 32 3b 0a 58 09 09 2a |+ = *ele|m2;.X..*|
|00001f90| 65 6c 65 6d 32 2b 2b 20 | 3d 20 74 65 6d 70 3b 0a |elem2++ |= temp;.|
|00001fa0| 58 09 7d 0a 58 0a 58 7d | 0a 58 0a 58 69 6e 74 20 |X.}.X.X}|.X.Xint |
|00001fb0| 69 6e 5f 6f 72 64 65 72 | 28 62 61 73 65 2c 20 6e |in_order|(base, n|
|00001fc0| 5f 65 6c 65 6d 2c 20 65 | 6c 65 6d 5f 73 69 7a 65 |_elem, e|lem_size|
|00001fd0| 2c 20 63 6f 6d 70 61 72 | 65 29 0a 58 20 20 20 72 |, compar|e).X r|
|00001fe0| 65 67 69 73 74 65 72 20 | 63 68 61 72 20 2a 62 61 |egister |char *ba|
|00001ff0| 73 65 3b 0a 58 20 20 20 | 72 65 67 69 73 74 65 72 |se;.X |register|
|00002000| 20 69 6e 74 20 6e 5f 65 | 6c 65 6d 3b 0a 58 20 20 | int n_e|lem;.X |
|00002010| 20 72 65 67 69 73 74 65 | 72 20 73 69 7a 65 5f 74 | registe|r size_t|
|00002020| 20 65 6c 65 6d 5f 73 69 | 7a 65 3b 0a 58 20 20 20 | elem_si|ze;.X |
|00002030| 69 6e 74 20 28 2a 63 6f | 6d 70 61 72 65 29 28 29 |int (*co|mpare)()|
|00002040| 3b 0a 58 7b 0a 58 09 77 | 68 69 6c 65 28 2d 2d 6e |;.X{.X.w|hile(--n|
|00002050| 5f 65 6c 65 6d 20 3e 20 | 30 29 0a 58 09 7b 0a 58 |_elem > |0).X.{.X|
|00002060| 09 09 69 66 28 63 6f 6d | 70 61 72 65 28 62 61 73 |..if(com|pare(bas|
|00002070| 65 2c 20 62 61 73 65 2b | 65 6c 65 6d 5f 73 69 7a |e, base+|elem_siz|
|00002080| 65 29 20 3e 20 30 29 0a | 58 09 09 09 72 65 74 75 |e) > 0).|X...retu|
|00002090| 72 6e 20 46 41 4c 53 45 | 3b 0a 58 09 09 62 61 73 |rn FALSE|;.X..bas|
|000020a0| 65 20 2b 3d 20 65 6c 65 | 6d 5f 73 69 7a 65 3b 0a |e += ele|m_size;.|
|000020b0| 58 09 7d 0a 58 09 72 65 | 74 75 72 6e 20 54 52 55 |X.}.X.re|turn TRU|
|000020c0| 45 3b 0a 58 7d 0a 58 0a | 58 2f 2a 0a 58 20 20 54 |E;.X}.X.|X/*.X T|
|000020d0| 68 65 20 62 6f 67 6f 28 | 29 20 66 75 6e 63 74 69 |he bogo(|) functi|
|000020e0| 6f 6e 3a 0a 58 0a 58 20 | 20 54 68 69 73 20 66 75 |on:.X.X | This fu|
|000020f0| 6e 63 74 69 6f 6e 20 69 | 73 20 63 61 6c 6c 65 64 |nction i|s called|
|00002100| 20 77 69 74 68 20 74 68 | 65 20 73 61 6d 65 20 61 | with th|e same a|
|00002110| 72 67 75 6d 65 6e 74 73 | 20 61 73 20 71 73 6f 72 |rguments| as qsor|
|00002120| 74 2e 20 20 57 68 65 6e | 20 69 74 20 72 65 74 75 |t. When| it retu|
|00002130| 72 6e 73 2c 0a 58 20 20 | 74 68 65 20 65 6c 65 6d |rns,.X |the elem|
|00002140| 65 6e 74 73 20 6f 66 20 | 74 68 65 20 67 69 76 65 |ents of |the give|
|00002150| 6e 20 61 72 72 61 79 20 | 61 72 65 20 69 6e 20 6f |n array |are in o|
|00002160| 72 64 65 72 2e 0a 58 0a | 58 20 20 59 6f 75 20 6d |rder..X.|X You m|
|00002170| 61 79 20 77 69 73 68 20 | 74 6f 20 63 61 6c 6c 20 |ay wish |to call |
|00002180| 73 72 61 6e 64 28 29 20 | 62 65 66 6f 72 65 20 75 |srand() |before u|
|00002190| 73 69 6e 67 20 62 6f 67 | 6f 73 6f 72 74 2e 0a 58 |sing bog|osort..X|
|000021a0| 2a 2f 0a 58 0a 58 69 6e | 74 20 62 6f 67 6f 5f 73 |*/.X.Xin|t bogo_s|
|000021b0| 6f 72 74 28 62 61 73 65 | 2c 20 6e 5f 65 6c 65 6d |ort(base|, n_elem|
|000021c0| 2c 20 65 6c 65 6d 5f 73 | 69 7a 65 2c 20 63 6f 6d |, elem_s|ize, com|
|000021d0| 70 61 72 65 29 0a 58 09 | 09 20 20 63 68 61 72 20 |pare).X.|. char |
|000021e0| 2a 62 61 73 65 3b 0a 58 | 09 09 20 20 69 6e 74 20 |*base;.X|.. int |
|000021f0| 6e 5f 65 6c 65 6d 3b 0a | 58 09 09 20 20 73 69 7a |n_elem;.|X.. siz|
|00002200| 65 5f 74 20 65 6c 65 6d | 5f 73 69 7a 65 3b 0a 58 |e_t elem|_size;.X|
|00002210| 09 09 20 20 69 6e 74 20 | 28 2a 63 6f 6d 70 61 72 |.. int |(*compar|
|00002220| 65 29 28 29 3b 0a 58 7b | 0a 58 09 61 73 73 65 72 |e)();.X{|.X.asser|
|00002230| 74 28 6e 5f 65 6c 65 6d | 20 3c 3d 20 52 41 4e 44 |t(n_elem| <= RAND|
|00002240| 5f 4d 41 58 29 3b 0a 58 | 0a 58 09 77 68 69 6c 65 |_MAX);.X|.X.while|
|00002250| 28 21 69 6e 5f 6f 72 64 | 65 72 28 62 61 73 65 2c |(!in_ord|er(base,|
|00002260| 20 6e 5f 65 6c 65 6d 2c | 20 65 6c 65 6d 5f 73 69 | n_elem,| elem_si|
|00002270| 7a 65 2c 20 63 6f 6d 70 | 61 72 65 29 29 0a 58 09 |ze, comp|are)).X.|
|00002280| 7b 0a 58 09 09 72 65 67 | 69 73 74 65 72 20 63 68 |{.X..reg|ister ch|
|00002290| 61 72 20 2a 65 6c 65 6d | 31 2c 20 2a 65 6c 65 6d |ar *elem|1, *elem|
|000022a0| 32 3b 0a 58 0a 58 09 09 | 65 6c 65 6d 31 20 3d 20 |2;.X.X..|elem1 = |
|000022b0| 62 61 73 65 20 2b 20 28 | 72 61 6e 67 65 5f 72 61 |base + (|range_ra|
|000022c0| 6e 64 28 6e 5f 65 6c 65 | 6d 29 20 2a 20 65 6c 65 |nd(n_ele|m) * ele|
|000022d0| 6d 5f 73 69 7a 65 29 3b | 0a 58 09 09 65 6c 65 6d |m_size);|.X..elem|
|000022e0| 32 20 3d 20 62 61 73 65 | 20 2b 20 28 72 61 6e 67 |2 = base| + (rang|
|000022f0| 65 5f 72 61 6e 64 28 6e | 5f 65 6c 65 6d 29 20 2a |e_rand(n|_elem) *|
|00002300| 20 65 6c 65 6d 5f 73 69 | 7a 65 29 3b 0a 58 0a 58 | elem_si|ze);.X.X|
|00002310| 09 09 73 77 61 70 5f 65 | 6c 65 6d 28 65 6c 65 6d |..swap_e|lem(elem|
|00002320| 31 2c 20 65 6c 65 6d 32 | 2c 20 65 6c 65 6d 5f 73 |1, elem2|, elem_s|
|00002330| 69 7a 65 29 3b 0a 58 09 | 7d 0a 58 7d 0a 58 0a 58 |ize);.X.|}.X}.X.X|
|00002340| 23 69 66 64 65 66 20 54 | 45 53 54 0a 58 0a 58 69 |#ifdef T|EST.X.Xi|
|00002350| 6e 74 20 61 72 72 61 79 | 5b 31 30 30 5d 3b 09 09 |nt array|[100];..|
|00002360| 2f 2a 20 55 70 20 74 6f | 20 31 30 30 20 65 6c 65 |/* Up to| 100 ele|
|00002370| 6d 65 6e 74 73 20 2d 20 | 6e 6f 20 66 75 72 74 68 |ments - |no furth|
|00002380| 65 72 20 2a 2f 0a 58 0a | 58 69 6e 74 20 69 6e 74 |er */.X.|Xint int|
|00002390| 5f 63 6f 6d 70 61 72 65 | 28 69 31 2c 20 69 32 29 |_compare|(i1, i2)|
|000023a0| 0a 58 20 20 63 68 61 72 | 20 2a 69 31 3b 20 63 68 |.X char| *i1; ch|
|000023b0| 61 72 20 2a 69 32 3b 0a | 58 7b 0a 58 09 72 65 74 |ar *i2;.|X{.X.ret|
|000023c0| 75 72 6e 20 2a 28 69 6e | 74 20 2a 29 69 31 20 2d |urn *(in|t *)i1 -|
|000023d0| 20 2a 28 69 6e 74 20 2a | 29 69 32 3b 0a 58 7d 0a | *(int *|)i2;.X}.|
|000023e0| 58 0a 58 6d 61 69 6e 28 | 61 72 67 63 2c 20 61 72 |X.Xmain(|argc, ar|
|000023f0| 67 76 29 0a 58 20 20 69 | 6e 74 20 61 72 67 63 3b |gv).X i|nt argc;|
|00002400| 20 63 68 61 72 20 2a 61 | 72 67 76 5b 5d 3b 0a 58 | char *a|rgv[];.X|
|00002410| 7b 0a 58 09 74 69 6d 65 | 5f 74 20 6e 6f 77 3b 0a |{.X.time|_t now;.|
|00002420| 58 09 69 6e 74 20 6e 5f | 65 6c 65 6d 3b 0a 58 09 |X.int n_|elem;.X.|
|00002430| 69 6e 74 20 69 3b 0a 58 | 0a 58 09 69 66 28 61 72 |int i;.X|.X.if(ar|
|00002440| 67 63 20 3c 20 32 29 0a | 58 09 7b 0a 58 09 09 66 |gc < 2).|X.{.X..f|
|00002450| 70 72 69 6e 74 66 28 73 | 74 64 65 72 72 2c 20 22 |printf(s|tderr, "|
|00002460| 75 73 65 61 67 65 3a 20 | 25 73 20 3c 6e 75 6d 62 |useage: |%s <numb|
|00002470| 65 72 20 6f 66 20 65 6c | 65 6d 65 6e 74 73 3e 5c |er of el|ements>\|
|00002480| 6e 22 2c 0a 58 09 09 09 | 09 61 72 67 76 5b 30 5d |n",.X...|.argv[0]|
|00002490| 29 3b 0a 58 09 09 65 78 | 69 74 28 45 58 49 54 5f |);.X..ex|it(EXIT_|
|000024a0| 46 41 49 4c 55 52 45 29 | 3b 0a 58 09 7d 0a 58 0a |FAILURE)|;.X.}.X.|
|000024b0| 58 09 6e 5f 65 6c 65 6d | 20 3d 20 61 74 6f 69 28 |X.n_elem| = atoi(|
|000024c0| 61 72 67 76 5b 31 5d 29 | 3b 0a 58 09 69 66 28 6e |argv[1])|;.X.if(n|
|000024d0| 5f 65 6c 65 6d 20 3e 20 | 31 30 30 29 0a 58 09 7b |_elem > |100).X.{|
|000024e0| 0a 58 09 09 66 70 72 69 | 6e 74 66 28 73 74 64 65 |.X..fpri|ntf(stde|
|000024f0| 72 72 2c 20 0a 58 20 20 | 22 4e 6f 20 6d 6f 72 65 |rr, .X |"No more|
|00002500| 20 74 68 61 6e 20 31 30 | 30 20 65 6c 65 6d 65 6e | than 10|0 elemen|
|00002510| 74 73 2c 20 70 6c 65 61 | 73 65 20 28 61 73 20 69 |ts, plea|se (as i|
|00002520| 66 20 79 6f 75 72 20 6c | 69 66 65 20 69 73 20 74 |f your l|ife is t|
|00002530| 68 61 74 20 6c 6f 6e 67 | 2e 2e 2e 29 5c 6e 22 29 |hat long|...)\n")|
|00002540| 3b 0a 58 09 09 65 78 69 | 74 28 45 58 49 54 5f 46 |;.X..exi|t(EXIT_F|
|00002550| 41 49 4c 55 52 45 29 3b | 0a 58 09 7d 0a 58 0a 58 |AILURE);|.X.}.X.X|
|00002560| 09 6e 6f 77 20 3d 20 74 | 69 6d 65 28 28 74 69 6d |.now = t|ime((tim|
|00002570| 65 5f 74 20 2a 29 4e 55 | 4c 4c 29 3b 0a 58 09 73 |e_t *)NU|LL);.X.s|
|00002580| 72 61 6e 64 6f 6d 28 6e | 6f 77 29 3b 0a 58 0a 58 |random(n|ow);.X.X|
|00002590| 09 66 70 75 74 73 28 22 | 53 74 61 72 74 69 6e 67 |.fputs("|Starting|
|000025a0| 20 61 72 72 61 79 3a 5c | 6e 22 2c 20 73 74 64 6f | array:\|n", stdo|
|000025b0| 75 74 29 3b 0a 58 0a 58 | 09 66 6f 72 28 69 20 3d |ut);.X.X|.for(i =|
|000025c0| 20 30 3b 20 69 20 3c 20 | 6e 5f 65 6c 65 6d 3b 20 | 0; i < |n_elem; |
|000025d0| 69 2b 2b 29 0a 58 09 7b | 0a 58 09 09 61 72 72 61 |i++).X.{|.X..arra|
|000025e0| 79 5b 69 5d 20 3d 20 72 | 61 6e 64 6f 6d 28 29 3b |y[i] = r|andom();|
|000025f0| 0a 58 09 09 70 72 69 6e | 74 66 28 22 25 64 20 22 |.X..prin|tf("%d "|
|00002600| 2c 20 61 72 72 61 79 5b | 69 5d 29 3b 0a 58 09 7d |, array[|i]);.X.}|
|00002610| 0a 58 09 66 70 75 74 73 | 28 22 5c 6e 22 2c 20 73 |.X.fputs|("\n", s|
|00002620| 74 64 6f 75 74 29 3b 0a | 58 0a 58 09 62 6f 67 6f |tdout);.|X.X.bogo|
|00002630| 5f 73 6f 72 74 28 28 63 | 68 61 72 20 2a 29 61 72 |_sort((c|har *)ar|
|00002640| 72 61 79 2c 20 6e 5f 65 | 6c 65 6d 2c 20 73 69 7a |ray, n_e|lem, siz|
|00002650| 65 6f 66 28 69 6e 74 29 | 2c 20 69 6e 74 5f 63 6f |eof(int)|, int_co|
|00002660| 6d 70 61 72 65 29 3b 0a | 58 0a 58 09 66 70 75 74 |mpare);.|X.X.fput|
|00002670| 73 28 22 45 6e 64 69 6e | 67 20 61 72 72 61 79 3a |s("Endin|g array:|
|00002680| 5c 6e 22 2c 20 73 74 64 | 6f 75 74 29 3b 0a 58 09 |\n", std|out);.X.|
|00002690| 66 6f 72 28 69 20 3d 20 | 30 3b 20 69 20 3c 20 6e |for(i = |0; i < n|
|000026a0| 5f 65 6c 65 6d 3b 20 69 | 2b 2b 29 0a 58 09 7b 0a |_elem; i|++).X.{.|
|000026b0| 58 09 09 70 72 69 6e 74 | 66 28 22 25 64 20 22 2c |X..print|f("%d ",|
|000026c0| 20 61 72 72 61 79 5b 69 | 5d 29 3b 0a 58 09 7d 0a | array[i|]);.X.}.|
|000026d0| 58 09 66 70 75 74 73 28 | 22 5c 6e 22 2c 20 73 74 |X.fputs(|"\n", st|
|000026e0| 64 6f 75 74 29 3b 0a 58 | 7d 0a 58 23 65 6e 64 69 |dout);.X|}.X#endi|
|000026f0| 66 0a 58 0a 45 4e 44 5f | 4f 46 5f 46 49 4c 45 0a |f.X.END_|OF_FILE.|
|00002700| 20 20 69 66 20 74 65 73 | 74 20 34 32 31 31 20 2d | if tes|t 4211 -|
|00002710| 6e 65 20 60 77 63 20 2d | 63 20 3c 27 62 6f 67 6f |ne `wc -|c <'bogo|
|00002720| 5f 73 6f 72 74 2e 63 27 | 60 3b 20 74 68 65 6e 0a |_sort.c'|`; then.|
|00002730| 20 20 20 20 65 63 68 6f | 20 73 68 61 72 3a 20 5c | echo| shar: \|
|00002740| 22 27 62 6f 67 6f 5f 73 | 6f 72 74 2e 63 27 5c 22 |"'bogo_s|ort.c'\"|
|00002750| 20 75 6e 70 61 63 6b 65 | 64 20 77 69 74 68 20 77 | unpacke|d with w|
|00002760| 72 6f 6e 67 20 73 69 7a | 65 21 0a 20 20 66 69 0a |rong siz|e!. fi.|
|00002770| 20 20 23 20 65 6e 64 20 | 6f 66 20 27 62 6f 67 6f | # end |of 'bogo|
|00002780| 5f 73 6f 72 74 2e 63 27 | 0a 66 69 0a 69 66 20 74 |_sort.c'|.fi.if t|
|00002790| 65 73 74 20 2d 66 20 27 | 62 75 62 62 6c 65 5f 73 |est -f '|bubble_s|
|000027a0| 6f 72 74 2e 63 27 20 2d | 61 20 22 24 7b 31 7d 22 |ort.c' -|a "${1}"|
|000027b0| 20 21 3d 20 22 2d 63 22 | 20 3b 20 74 68 65 6e 20 | != "-c"| ; then |
|000027c0| 0a 20 20 65 63 68 6f 20 | 73 68 61 72 3a 20 57 69 |. echo |shar: Wi|
|000027d0| 6c 6c 20 6e 6f 74 20 63 | 6c 6f 62 62 65 72 20 65 |ll not c|lobber e|
|000027e0| 78 69 73 74 69 6e 67 20 | 66 69 6c 65 20 5c 22 27 |xisting |file \"'|
|000027f0| 62 75 62 62 6c 65 5f 73 | 6f 72 74 2e 63 27 5c 22 |bubble_s|ort.c'\"|
|00002800| 0a 65 6c 73 65 0a 20 20 | 65 63 68 6f 20 73 68 61 |.else. |echo sha|
|00002810| 72 3a 20 45 78 74 72 61 | 63 74 69 6e 67 20 5c 22 |r: Extra|cting \"|
|00002820| 27 62 75 62 62 6c 65 5f | 73 6f 72 74 2e 63 27 5c |'bubble_|sort.c'\|
|00002830| 22 20 5c 28 33 33 38 39 | 20 63 68 61 72 61 63 74 |" \(3389| charact|
|00002840| 65 72 73 5c 29 0a 20 20 | 73 65 64 20 22 73 2f 5e |ers\). |sed "s/^|
|00002850| 58 2f 2f 22 20 3e 27 62 | 75 62 62 6c 65 5f 73 6f |X//" >'b|ubble_so|
|00002860| 72 74 2e 63 27 20 3c 3c | 27 45 4e 44 5f 4f 46 5f |rt.c' <<|'END_OF_|
|00002870| 46 49 4c 45 27 0a 58 0a | 58 2f 2a 20 0a 58 0a 58 |FILE'.X.|X/* .X.X|
|00002880| 4e 41 4d 45 0a 58 20 20 | 62 75 62 62 6c 65 20 73 |NAME.X |bubble s|
|00002890| 6f 72 74 0a 58 0a 58 44 | 45 53 43 52 49 50 54 49 |ort.X.XD|ESCRIPTI|
|000028a0| 4f 4e 0a 58 0a 58 20 20 | 54 72 61 69 70 73 65 20 |ON.X.X |Traipse |
|000028b0| 75 70 20 61 6e 64 20 64 | 6f 77 6e 20 74 68 65 20 |up and d|own the |
|000028c0| 72 65 63 6f 72 64 73 20 | 75 6e 74 69 6c 20 74 68 |records |until th|
|000028d0| 65 20 65 6e 74 69 72 65 | 20 61 72 72 61 79 20 69 |e entire| array i|
|000028e0| 73 20 69 6e 20 6f 72 64 | 65 72 0a 58 20 20 65 78 |s in ord|er.X ex|
|000028f0| 63 68 61 6e 67 69 6e 67 | 20 72 65 63 6f 72 64 73 |changing| records|
|00002900| 20 77 69 74 68 20 74 68 | 65 69 72 20 6e 65 69 67 | with th|eir neig|
|00002910| 68 62 6f 72 73 20 69 66 | 20 74 68 65 20 61 64 6a |hbors if| the adj|
|00002920| 61 63 65 6e 74 20 72 65 | 63 6f 72 64 73 20 61 72 |acent re|cords ar|
|00002930| 65 0a 58 20 20 6f 75 74 | 20 6f 66 20 6f 72 64 65 |e.X out| of orde|
|00002940| 72 20 77 69 74 68 20 72 | 65 73 70 65 63 74 20 74 |r with r|espect t|
|00002950| 6f 20 65 61 63 68 20 6f | 74 68 65 72 2e 20 20 41 |o each o|ther. A|
|00002960| 20 66 6c 61 67 20 6b 65 | 65 70 73 20 74 72 61 63 | flag ke|eps trac|
|00002970| 6b 20 6f 66 0a 58 20 20 | 77 68 65 74 68 65 72 20 |k of.X |whether |
|00002980| 65 78 63 68 61 6e 67 65 | 73 20 77 65 72 65 20 64 |exchange|s were d|
|00002990| 6f 6e 65 3b 20 77 68 65 | 6e 20 61 6e 20 65 6e 74 |one; whe|n an ent|
|000029a0| 69 72 65 20 70 61 73 73 | 20 69 73 20 6d 61 64 65 |ire pass| is made|
|000029b0| 20 61 6e 64 20 6e 6f 0a | 58 20 20 65 78 63 68 61 | and no.|X excha|
|000029c0| 6e 67 65 73 20 77 65 72 | 65 20 70 65 72 66 6f 72 |nges wer|e perfor|
|000029d0| 6d 65 64 2c 20 74 68 65 | 20 73 6f 72 74 20 69 73 |med, the| sort is|
|000029e0| 20 63 6f 6d 70 6c 65 74 | 65 2e 20 20 41 6c 73 6f | complet|e. Also|
|000029f0| 2c 20 61 66 74 65 72 20 | 65 61 63 68 0a 58 20 20 |, after |each.X |
|00002a00| 70 61 73 73 2c 20 74 68 | 65 20 65 6c 65 6d 65 6e |pass, th|e elemen|
|00002a10| 74 20 61 74 20 74 68 65 | 20 65 6e 64 20 6f 66 20 |t at the| end of |
|00002a20| 74 68 65 20 70 61 73 73 | 20 69 73 20 67 75 61 72 |the pass| is guar|
|00002a30| 61 6e 74 65 65 64 20 74 | 6f 20 62 65 20 69 6e 20 |anteed t|o be in |
|00002a40| 69 74 27 73 0a 58 20 20 | 66 69 6e 61 6c 20 70 6c |it's.X |final pl|
|00002a50| 61 63 65 20 73 6f 20 74 | 68 65 20 6e 65 78 74 20 |ace so t|he next |
|00002a60| 70 61 73 73 20 65 78 63 | 6c 75 64 65 73 20 69 74 |pass exc|ludes it|
|00002a70| 2e 0a 58 0a 58 20 20 54 | 68 69 73 20 61 6c 67 6f |..X.X T|his algo|
|00002a80| 72 69 74 68 6d 20 72 65 | 76 65 72 73 65 73 20 64 |rithm re|verses d|
|00002a90| 69 72 65 63 74 69 6f 6e | 20 6f 6e 20 65 61 63 68 |irection| on each|
|00002aa0| 20 70 61 73 73 2c 20 73 | 6f 20 74 68 61 74 20 61 | pass, s|o that a|
|00002ab0| 20 73 69 6e 67 6c 65 20 | 69 74 65 6d 0a 58 20 20 | single |item.X |
|00002ac0| 6f 75 74 20 6f 66 20 6f | 72 64 65 72 20 77 6f 6e |out of o|rder won|
|00002ad0| 27 74 20 66 6f 72 63 65 | 20 77 6f 72 73 74 2d 63 |'t force| worst-c|
|00002ae0| 61 73 65 20 62 65 68 61 | 76 69 6f 72 2e 20 20 4b |ase beha|vior. K|
|00002af0| 6e 75 74 68 20 72 65 66 | 65 72 73 20 74 6f 20 74 |nuth ref|ers to t|
|00002b00| 68 69 73 0a 58 20 20 61 | 73 20 74 68 65 20 22 63 |his.X a|s the "c|
|00002b10| 6f 63 6b 74 61 69 6c 20 | 73 68 61 6b 65 72 20 73 |ocktail |shaker s|
|00002b20| 6f 72 74 2e 22 0a 58 0a | 58 41 55 54 48 4f 52 53 |ort.".X.|XAUTHORS|
|00002b30| 48 49 50 0a 58 0a 58 20 | 20 55 6e 6b 6e 6f 77 6e |HIP.X.X | Unknown|
|00002b40| 20 74 6f 20 6d 65 2e 0a | 58 0a 58 52 45 46 45 52 | to me..|X.XREFER|
|00002b50| 45 4e 43 45 53 0a 58 0a | 58 20 20 4b 6e 75 74 68 |ENCES.X.|X Knuth|
|00002b60| 20 56 6f 6c 20 33 2c 20 | 70 61 67 65 20 31 30 36 | Vol 3, |page 106|
|00002b70| 2d 31 31 31 0a 58 0a 58 | 43 4f 4d 50 4c 45 58 49 |-111.X.X|COMPLEXI|
|00002b80| 54 59 0a 58 0a 58 20 20 | 42 65 73 74 20 63 61 73 |TY.X.X |Best cas|
|00002b90| 65 20 4f 28 6e 29 0a 58 | 20 20 57 6f 72 73 74 20 |e O(n).X| Worst |
|00002ba0| 63 61 73 65 20 4f 28 6e | 5e 32 29 0a 58 20 20 49 |case O(n|^2).X I|
|00002bb0| 74 65 72 61 74 69 76 65 | 2e 0a 58 0a 58 43 4f 50 |terative|..X.XCOP|
|00002bc0| 59 52 49 47 48 54 0a 58 | 0a 58 20 20 43 6f 70 79 |YRIGHT.X|.X Copy|
|00002bd0| 72 69 67 68 74 20 31 39 | 39 32 20 4d 69 63 68 61 |right 19|92 Micha|
|00002be0| 65 6c 20 4c 65 65 2e 0a | 58 0a 58 20 20 28 31 29 |el Lee..|X.X (1)|
|00002bf0| 20 50 65 72 6d 69 73 73 | 69 6f 6e 20 74 6f 20 75 | Permiss|ion to u|
|00002c00| 73 65 2c 20 63 6f 70 79 | 2c 20 64 69 73 74 72 69 |se, copy|, distri|
|00002c10| 62 75 74 65 2c 20 61 6e | 64 20 6d 61 6b 65 20 63 |bute, an|d make c|
|00002c20| 68 61 6e 67 65 73 20 69 | 73 20 67 72 61 6e 74 65 |hanges i|s grante|
|00002c30| 64 0a 58 20 20 70 72 6f | 76 69 64 69 6e 67 20 74 |d.X pro|viding t|
|00002c40| 68 61 74 20 28 61 29 20 | 74 68 61 74 20 79 6f 75 |hat (a) |that you|
|00002c50| 20 64 6f 20 73 6f 20 77 | 69 74 68 6f 75 74 20 63 | do so w|ithout c|
|00002c60| 68 61 72 67 69 6e 67 20 | 61 6e 79 6f 6e 65 20 61 |harging |anyone a|
|00002c70| 20 66 65 65 20 61 6e 64 | 0a 58 20 20 28 62 29 20 | fee and|.X (b) |
|00002c80| 74 68 69 73 20 63 6f 70 | 79 72 69 67 68 74 20 6e |this cop|yright n|
|00002c90| 6f 74 69 63 65 20 6d 75 | 73 74 20 62 65 20 69 6e |otice mu|st be in|
|00002ca0| 63 6c 75 64 65 64 20 76 | 65 72 62 61 74 69 6d 20 |cluded v|erbatim |
|00002cb0| 69 6e 20 61 6c 6c 20 63 | 6f 70 69 65 73 20 61 6e |in all c|opies an|
|00002cc0| 64 20 0a 58 20 20 64 69 | 73 74 72 69 62 75 74 69 |d .X di|stributi|
|00002cd0| 6f 6e 73 2e 20 20 0a 58 | 0a 58 20 20 28 32 29 20 |ons. .X|.X (2) |
|00002ce0| 54 68 65 72 65 20 69 73 | 20 6e 6f 20 77 61 72 72 |There is| no warr|
|00002cf0| 61 6e 74 79 20 66 6f 72 | 20 74 68 69 73 20 70 72 |anty for| this pr|
|00002d00| 6f 67 72 61 6d 2c 20 74 | 6f 20 74 68 65 20 65 78 |ogram, t|o the ex|
|00002d10| 74 65 6e 74 20 70 65 72 | 6d 69 74 74 65 64 20 62 |tent per|mitted b|
|00002d20| 79 0a 58 20 20 61 70 70 | 6c 69 63 61 62 6c 65 20 |y.X app|licable |
|00002d30| 6c 61 77 2e 20 20 54 68 | 69 73 20 70 72 6f 67 72 |law. Th|is progr|
|00002d40| 61 6d 20 69 73 20 70 72 | 6f 76 69 64 65 64 20 22 |am is pr|ovided "|
|00002d50| 41 53 20 49 53 22 20 77 | 69 74 68 6f 75 74 20 77 |AS IS" w|ithout w|
|00002d60| 61 72 72 61 6e 74 79 20 | 6f 66 0a 58 20 20 61 6e |arranty |of.X an|
|00002d70| 79 20 6b 69 6e 64 2c 20 | 65 69 74 68 65 72 20 65 |y kind, |either e|
|00002d80| 78 70 72 65 73 73 65 64 | 20 6f 72 20 69 6d 70 6c |xpressed| or impl|
|00002d90| 69 65 64 2c 20 69 6e 63 | 6c 75 64 69 6e 67 2c 20 |ied, inc|luding, |
|00002da0| 62 75 74 20 6e 6f 74 20 | 6c 69 6d 69 74 65 64 20 |but not |limited |
|00002db0| 74 6f 2c 0a 58 20 20 74 | 68 65 20 69 6d 70 6c 69 |to,.X t|he impli|
|00002dc0| 65 64 20 77 61 72 72 61 | 6e 74 69 65 73 20 6f 66 |ed warra|nties of|
|00002dd0| 20 6d 65 72 63 68 61 6e | 74 61 62 69 6c 69 74 79 | merchan|tability|
|00002de0| 20 61 6e 64 20 66 69 74 | 6e 65 73 73 20 66 6f 72 | and fit|ness for|
|00002df0| 20 61 20 70 61 72 74 69 | 63 75 6c 61 72 20 0a 58 | a parti|cular .X|
|00002e00| 20 20 70 75 72 70 6f 73 | 65 2e 20 20 54 68 65 20 | purpos|e. The |
|00002e10| 65 6e 74 69 72 65 20 72 | 69 73 6b 20 61 73 20 74 |entire r|isk as t|
|00002e20| 6f 20 74 68 65 20 71 75 | 61 6c 69 74 79 20 61 6e |o the qu|ality an|
|00002e30| 64 20 70 65 72 66 6f 72 | 6d 61 6e 63 65 20 6f 66 |d perfor|mance of|
|00002e40| 20 74 68 69 73 20 0a 58 | 20 20 70 72 6f 67 72 61 | this .X| progra|
|00002e50| 6d 20 69 73 20 77 69 74 | 68 20 74 68 65 20 75 73 |m is wit|h the us|
|00002e60| 65 72 2e 20 20 53 68 6f | 75 6c 64 20 74 68 69 73 |er. Sho|uld this|
|00002e70| 20 70 72 6f 67 72 61 6d | 20 70 72 6f 76 65 20 64 | program| prove d|
|00002e80| 65 66 65 63 74 69 76 65 | 2c 20 74 68 65 20 0a 58 |efective|, the .X|
|00002e90| 20 20 75 73 65 72 20 61 | 73 73 75 6d 65 73 20 74 | user a|ssumes t|
|00002ea0| 68 65 20 63 6f 73 74 20 | 6f 66 20 61 6c 6c 20 6e |he cost |of all n|
|00002eb0| 65 63 65 73 73 61 72 79 | 20 73 65 72 76 69 63 69 |ecessary| servici|
|00002ec0| 6e 67 2c 20 72 65 70 61 | 69 72 20 6f 72 20 63 6f |ng, repa|ir or co|
|00002ed0| 72 72 65 63 74 69 6f 6e | 2e 0a 58 0a 58 20 20 28 |rrection|..X.X (|
|00002ee0| 33 29 20 49 6e 20 6e 6f | 20 65 76 65 6e 74 20 75 |3) In no| event u|
|00002ef0| 6e 6c 65 73 73 20 72 65 | 71 75 69 72 65 64 20 62 |nless re|quired b|
|00002f00| 79 20 61 70 70 6c 69 63 | 61 62 6c 65 20 6c 61 77 |y applic|able law|
|00002f10| 20 77 69 6c 6c 20 74 68 | 65 20 63 6f 70 79 72 69 | will th|e copyri|
|00002f20| 67 68 74 0a 58 20 20 68 | 6f 6c 64 65 72 20 62 65 |ght.X h|older be|
|00002f30| 20 6c 69 61 62 6c 65 20 | 74 6f 20 74 68 65 20 75 | liable |to the u|
|00002f40| 73 65 72 20 66 6f 72 20 | 64 61 6d 61 67 65 73 2c |ser for |damages,|
|00002f50| 20 69 6e 63 6c 75 64 69 | 6e 67 20 61 6e 79 20 67 | includi|ng any g|
|00002f60| 65 6e 65 72 61 6c 2c 0a | 58 20 20 73 70 65 63 69 |eneral,.|X speci|
|00002f70| 61 6c 2c 20 69 6e 63 69 | 64 65 6e 74 61 6c 20 6f |al, inci|dental o|
|00002f80| 72 20 63 6f 6e 73 65 71 | 75 65 6e 74 69 61 6c 20 |r conseq|uential |
|00002f90| 64 61 6d 61 67 65 73 20 | 61 72 69 73 69 6e 67 20 |damages |arising |
|00002fa0| 6f 75 74 20 6f 66 20 74 | 68 65 20 75 73 65 0a 58 |out of t|he use.X|
|00002fb0| 20 20 6f 72 20 69 6e 61 | 62 69 6c 69 74 79 20 74 | or ina|bility t|
|00002fc0| 6f 20 75 73 65 20 74 68 | 69 73 20 70 72 6f 67 72 |o use th|is progr|
|00002fd0| 61 6d 20 28 69 6e 63 6c | 75 64 69 6e 67 20 62 75 |am (incl|uding bu|
|00002fe0| 74 20 6e 6f 74 20 6c 69 | 6d 69 74 65 64 20 74 6f |t not li|mited to|
|00002ff0| 20 6c 6f 73 73 20 6f 66 | 0a 58 20 20 64 61 74 61 | loss of|.X data|
|00003000| 20 6f 72 20 64 61 74 61 | 20 62 65 69 6e 67 20 72 | or data| being r|
|00003010| 65 6e 64 65 72 65 64 20 | 69 6e 61 63 63 75 72 61 |endered |inaccura|
|00003020| 74 65 20 6f 72 20 6c 6f | 73 73 65 73 20 73 75 73 |te or lo|sses sus|
|00003030| 74 61 69 6e 65 64 20 62 | 79 20 74 68 65 0a 58 20 |tained b|y the.X |
|00003040| 20 75 73 65 72 20 6f 72 | 20 74 68 69 72 64 20 70 | user or| third p|
|00003050| 61 72 74 69 65 73 20 6f | 72 20 61 20 66 61 69 6c |arties o|r a fail|
|00003060| 75 72 65 20 6f 66 20 74 | 68 69 73 20 70 72 6f 67 |ure of t|his prog|
|00003070| 72 61 6d 20 74 6f 20 6f | 70 65 72 61 74 65 20 77 |ram to o|perate w|
|00003080| 69 74 68 20 61 6e 79 0a | 58 20 20 6f 74 68 65 72 |ith any.|X other|
|00003090| 20 70 72 6f 67 72 61 6d | 73 29 2c 20 65 76 65 6e | program|s), even|
|000030a0| 20 69 66 20 73 75 63 68 | 20 68 6f 6c 64 65 72 20 | if such| holder |
|000030b0| 6f 72 20 74 68 69 72 64 | 20 70 61 72 74 79 20 68 |or third| party h|
|000030c0| 61 73 20 62 65 65 6e 20 | 61 64 76 69 73 65 64 0a |as been |advised.|
|000030d0| 58 20 20 6f 66 20 74 68 | 65 20 70 6f 73 73 69 62 |X of th|e possib|
|000030e0| 69 6c 69 74 79 20 6f 66 | 20 73 75 63 68 20 64 61 |ility of| such da|
|000030f0| 6d 61 67 65 73 2e 0a 58 | 0a 58 20 20 28 34 29 20 |mages..X|.X (4) |
|00003100| 4f 62 6a 65 63 74 20 63 | 6f 64 65 20 70 72 6f 64 |Object c|ode prod|
|00003110| 75 63 65 64 20 62 79 20 | 61 20 63 6f 6d 70 69 6c |uced by |a compil|
|00003120| 65 72 20 66 72 6f 6d 20 | 74 68 69 73 20 63 6f 64 |er from |this cod|
|00003130| 65 20 6d 61 79 20 62 65 | 20 0a 58 20 20 69 6e 63 |e may be| .X inc|
|00003140| 6f 72 70 6f 72 61 74 65 | 64 20 69 6e 74 6f 20 63 |orporate|d into c|
|00003150| 6f 6d 6d 65 72 63 69 61 | 6c 20 70 72 6f 64 75 63 |ommercia|l produc|
|00003160| 74 73 20 77 69 74 68 6f | 75 74 20 62 65 69 6e 67 |ts witho|ut being|
|00003170| 20 73 75 62 6a 65 63 74 | 20 74 6f 20 0a 58 20 20 | subject| to .X |
|00003180| 72 65 73 74 72 69 63 74 | 69 6f 6e 73 20 28 31 29 |restrict|ions (1)|
|00003190| 28 61 29 20 6f 72 20 28 | 31 29 28 62 29 2e 0a 58 |(a) or (|1)(b)..X|
|000031a0| 0a 58 2a 2f 0a 58 0a 58 | 23 69 6e 63 6c 75 64 65 |.X*/.X.X|#include|
|000031b0| 20 3c 73 74 64 69 6f 2e | 68 3e 0a 58 23 69 6e 63 | <stdio.|h>.X#inc|
|000031c0| 6c 75 64 65 20 3c 6d 61 | 6c 6c 6f 63 2e 68 3e 0a |lude <ma|lloc.h>.|
|000031d0| 58 23 69 6e 63 6c 75 64 | 65 20 3c 6d 65 6d 6f 72 |X#includ|e <memor|
|000031e0| 79 2e 68 3e 0a 58 23 69 | 6e 63 6c 75 64 65 20 3c |y.h>.X#i|nclude <|
|000031f0| 73 74 72 69 6e 67 2e 68 | 3e 0a 58 23 69 6e 63 6c |string.h|>.X#incl|
|00003200| 75 64 65 20 3c 61 73 73 | 65 72 74 2e 68 3e 0a 58 |ude <ass|ert.h>.X|
|00003210| 0a 58 23 69 6e 63 6c 75 | 64 65 20 22 73 6f 72 74 |.X#inclu|de "sort|
|00003220| 69 6e 67 2e 68 22 0a 58 | 0a 58 69 6e 74 20 62 75 |ing.h".X|.Xint bu|
|00003230| 62 62 6c 65 5f 73 6f 72 | 74 28 62 61 73 65 2c 20 |bble_sor|t(base, |
|00003240| 6e 65 6c 65 6d 2c 20 77 | 69 64 74 68 2c 20 63 6d |nelem, w|idth, cm|
|00003250| 70 72 5f 66 75 6e 63 29 | 0a 58 20 20 63 68 61 72 |pr_func)|.X char|
|00003260| 20 2a 20 62 61 73 65 3b | 0a 58 20 20 69 6e 74 20 | * base;|.X int |
|00003270| 6e 65 6c 65 6d 3b 0a 58 | 20 20 69 6e 74 20 77 69 |nelem;.X| int wi|
|00003280| 64 74 68 3b 0a 58 20 20 | 69 6e 74 20 28 2a 63 6d |dth;.X |int (*cm|
|00003290| 70 72 5f 66 75 6e 63 29 | 28 29 3b 0a 58 7b 0a 58 |pr_func)|();.X{.X|
|000032a0| 20 20 69 6e 74 20 74 6f | 70 20 3d 20 6e 65 6c 65 | int to|p = nele|
|000032b0| 6d 20 2d 20 31 3b 0a 58 | 20 20 69 6e 74 20 62 6f |m - 1;.X| int bo|
|000032c0| 74 74 6f 6d 20 3d 20 30 | 3b 0a 58 20 20 69 6e 74 |ttom = 0|;.X int|
|000032d0| 20 69 2c 20 64 69 64 5f | 73 77 61 70 20 3d 20 31 | i, did_|swap = 1|
|000032e0| 3b 0a 58 20 20 63 68 61 | 72 20 2a 20 74 65 6d 70 |;.X cha|r * temp|
|000032f0| 3b 0a 58 0a 58 20 20 74 | 65 6d 70 20 3d 20 6d 61 |;.X.X t|emp = ma|
|00003300| 6c 6c 6f 63 28 77 69 64 | 74 68 29 3b 0a 58 20 20 |lloc(wid|th);.X |
|00003310| 61 73 73 65 72 74 28 74 | 65 6d 70 20 21 3d 20 4e |assert(t|emp != N|
|00003320| 55 4c 4c 29 3b 0a 58 0a | 58 20 20 77 68 69 6c 65 |ULL);.X.|X while|
|00003330| 20 28 74 6f 70 20 3e 20 | 62 6f 74 74 6f 6d 29 0a | (top > |bottom).|
|00003340| 58 20 20 7b 0a 58 20 20 | 20 20 64 69 64 5f 73 77 |X {.X | did_sw|
|00003350| 61 70 20 3d 20 30 3b 0a | 58 20 20 20 20 66 6f 72 |ap = 0;.|X for|
|00003360| 20 28 69 20 3d 20 62 6f | 74 74 6f 6d 3b 20 69 20 | (i = bo|ttom; i |
|00003370| 3c 20 74 6f 70 3b 20 69 | 2b 2b 29 0a 58 20 20 20 |< top; i|++).X |
|00003380| 20 20 20 69 66 20 28 28 | 2a 63 6d 70 72 5f 66 75 | if ((|*cmpr_fu|
|00003390| 6e 63 29 28 62 61 73 65 | 2b 69 2a 77 69 64 74 68 |nc)(base|+i*width|
|000033a0| 2c 20 62 61 73 65 2b 28 | 69 2b 31 29 2a 77 69 64 |, base+(|i+1)*wid|
|000033b0| 74 68 29 20 3e 20 30 29 | 0a 58 20 20 20 20 20 20 |th) > 0)|.X |
|000033c0| 7b 0a 58 20 20 20 20 20 | 20 20 20 6d 65 6d 63 70 |{.X | memcp|
|000033d0| 79 28 74 65 6d 70 2c 20 | 62 61 73 65 2b 69 2a 77 |y(temp, |base+i*w|
|000033e0| 69 64 74 68 2c 20 77 69 | 64 74 68 29 3b 0a 58 20 |idth, wi|dth);.X |
|000033f0| 20 20 20 20 20 20 20 6d | 65 6d 63 70 79 28 62 61 | m|emcpy(ba|
|00003400| 73 65 2b 69 2a 77 69 64 | 74 68 2c 20 62 61 73 65 |se+i*wid|th, base|
|00003410| 2b 28 69 2b 31 29 2a 77 | 69 64 74 68 2c 20 77 69 |+(i+1)*w|idth, wi|
|00003420| 64 74 68 29 3b 0a 58 20 | 20 20 20 20 20 20 20 6d |dth);.X | m|
|00003430| 65 6d 63 70 79 28 62 61 | 73 65 2b 28 69 2b 31 29 |emcpy(ba|se+(i+1)|
|00003440| 2a 77 69 64 74 68 2c 20 | 74 65 6d 70 2c 20 77 69 |*width, |temp, wi|
|00003450| 64 74 68 29 3b 0a 58 20 | 20 20 20 20 20 20 20 64 |dth);.X | d|
|00003460| 69 64 5f 73 77 61 70 20 | 3d 20 31 3b 0a 58 20 20 |id_swap |= 1;.X |
|00003470| 20 20 20 20 7d 0a 58 0a | 58 20 20 20 20 69 66 20 | }.X.|X if |
|00003480| 28 21 64 69 64 5f 73 77 | 61 70 29 20 62 72 65 61 |(!did_sw|ap) brea|
|00003490| 6b 3b 0a 58 20 20 20 20 | 74 6f 70 2d 2d 3b 0a 58 |k;.X |top--;.X|
|000034a0| 0a 58 20 20 20 20 64 69 | 64 5f 73 77 61 70 20 3d |.X di|d_swap =|
|000034b0| 20 30 3b 0a 58 20 20 20 | 20 66 6f 72 20 28 69 20 | 0;.X | for (i |
|000034c0| 3d 20 74 6f 70 20 2d 20 | 31 3b 20 69 20 3e 3d 20 |= top - |1; i >= |
|000034d0| 62 6f 74 74 6f 6d 3b 20 | 69 2d 2d 29 0a 58 20 20 |bottom; |i--).X |
|000034e0| 20 20 20 20 69 66 20 28 | 28 2a 63 6d 70 72 5f 66 | if (|(*cmpr_f|
|000034f0| 75 6e 63 29 28 62 61 73 | 65 2b 69 2a 77 69 64 74 |unc)(bas|e+i*widt|
|00003500| 68 2c 20 62 61 73 65 2b | 28 69 2b 31 29 2a 77 69 |h, base+|(i+1)*wi|
|00003510| 64 74 68 29 20 3e 20 30 | 29 0a 58 20 20 20 20 20 |dth) > 0|).X |
|00003520| 20 7b 0a 58 20 20 20 20 | 20 20 20 20 6d 65 6d 63 | {.X | memc|
|00003530| 70 79 28 74 65 6d 70 2c | 20 62 61 73 65 2b 69 2a |py(temp,| base+i*|
|00003540| 77 69 64 74 68 2c 20 77 | 69 64 74 68 29 3b 0a 58 |width, w|idth);.X|
|00003550| 20 20 20 20 20 20 20 20 | 6d 65 6d 63 70 79 28 62 | |memcpy(b|
|00003560| 61 73 65 2b 69 2a 77 69 | 64 74 68 2c 20 62 61 73 |ase+i*wi|dth, bas|
|00003570| 65 2b 28 69 2b 31 29 2a | 77 69 64 74 68 2c 20 77 |e+(i+1)*|width, w|
|00003580| 69 64 74 68 29 3b 0a 58 | 20 20 20 20 20 20 20 20 |idth);.X| |
|00003590| 6d 65 6d 63 70 79 28 62 | 61 73 65 2b 28 69 2b 31 |memcpy(b|ase+(i+1|
|000035a0| 29 2a 77 69 64 74 68 2c | 20 74 65 6d 70 2c 20 77 |)*width,| temp, w|
|000035b0| 69 64 74 68 29 3b 0a 58 | 20 20 20 20 20 20 20 20 |idth);.X| |
|000035c0| 64 69 64 5f 73 77 61 70 | 20 3d 20 31 3b 0a 58 20 |did_swap| = 1;.X |
|000035d0| 20 20 20 20 20 7d 0a 58 | 0a 58 20 20 20 20 69 66 | }.X|.X if|
|000035e0| 20 28 21 64 69 64 5f 73 | 77 61 70 29 20 62 72 65 | (!did_s|wap) bre|
|000035f0| 61 6b 3b 0a 58 20 20 20 | 20 62 6f 74 74 6f 6d 20 |ak;.X | bottom |
|00003600| 2b 2b 3b 0a 58 20 20 7d | 0a 58 0a 58 20 20 66 72 |++;.X }|.X.X fr|
|00003610| 65 65 28 74 65 6d 70 29 | 3b 0a 58 20 20 72 65 74 |ee(temp)|;.X ret|
|00003620| 75 72 6e 20 30 3b 0a 58 | 0a 58 7d 0a 45 4e 44 5f |urn 0;.X|.X}.END_|
|00003630| 4f 46 5f 46 49 4c 45 0a | 20 20 69 66 20 74 65 73 |OF_FILE.| if tes|
|00003640| 74 20 33 33 38 39 20 2d | 6e 65 20 60 77 63 20 2d |t 3389 -|ne `wc -|
|00003650| 63 20 3c 27 62 75 62 62 | 6c 65 5f 73 6f 72 74 2e |c <'bubb|le_sort.|
|00003660| 63 27 60 3b 20 74 68 65 | 6e 0a 20 20 20 20 65 63 |c'`; the|n. ec|
|00003670| 68 6f 20 73 68 61 72 3a | 20 5c 22 27 62 75 62 62 |ho shar:| \"'bubb|
|00003680| 6c 65 5f 73 6f 72 74 2e | 63 27 5c 22 20 75 6e 70 |le_sort.|c'\" unp|
|00003690| 61 63 6b 65 64 20 77 69 | 74 68 20 77 72 6f 6e 67 |acked wi|th wrong|
|000036a0| 20 73 69 7a 65 21 0a 20 | 20 66 69 0a 20 20 23 20 | size!. | fi. # |
|000036b0| 65 6e 64 20 6f 66 20 27 | 62 75 62 62 6c 65 5f 73 |end of '|bubble_s|
|000036c0| 6f 72 74 2e 63 27 0a 66 | 69 0a 69 66 20 74 65 73 |ort.c'.f|i.if tes|
|000036d0| 74 20 2d 66 20 27 69 6e | 73 65 72 74 5f 73 6f 72 |t -f 'in|sert_sor|
|000036e0| 74 2e 63 27 20 2d 61 20 | 22 24 7b 31 7d 22 20 21 |t.c' -a |"${1}" !|
|000036f0| 3d 20 22 2d 63 22 20 3b | 20 74 68 65 6e 20 0a 20 |= "-c" ;| then . |
|00003700| 20 65 63 68 6f 20 73 68 | 61 72 3a 20 57 69 6c 6c | echo sh|ar: Will|
|00003710| 20 6e 6f 74 20 63 6c 6f | 62 62 65 72 20 65 78 69 | not clo|bber exi|
|00003720| 73 74 69 6e 67 20 66 69 | 6c 65 20 5c 22 27 69 6e |sting fi|le \"'in|
|00003730| 73 65 72 74 5f 73 6f 72 | 74 2e 63 27 5c 22 0a 65 |sert_sor|t.c'\".e|
|00003740| 6c 73 65 0a 20 20 65 63 | 68 6f 20 73 68 61 72 3a |lse. ec|ho shar:|
|00003750| 20 45 78 74 72 61 63 74 | 69 6e 67 20 5c 22 27 69 | Extract|ing \"'i|
|00003760| 6e 73 65 72 74 5f 73 6f | 72 74 2e 63 27 5c 22 20 |nsert_so|rt.c'\" |
|00003770| 5c 28 33 32 39 38 20 63 | 68 61 72 61 63 74 65 72 |\(3298 c|haracter|
|00003780| 73 5c 29 0a 20 20 73 65 | 64 20 22 73 2f 5e 58 2f |s\). se|d "s/^X/|
|00003790| 2f 22 20 3e 27 69 6e 73 | 65 72 74 5f 73 6f 72 74 |/" >'ins|ert_sort|
|000037a0| 2e 63 27 20 3c 3c 27 45 | 4e 44 5f 4f 46 5f 46 49 |.c' <<'E|ND_OF_FI|
|000037b0| 4c 45 27 0a 58 0a 58 2f | 2a 20 0a 58 0a 58 4e 41 |LE'.X.X/|* .X.XNA|
|000037c0| 4d 45 0a 58 20 20 69 6e | 73 65 72 74 69 6f 6e 20 |ME.X in|sertion |
|000037d0| 73 6f 72 74 20 0a 58 0a | 58 44 45 53 43 52 49 50 |sort .X.|XDESCRIP|
|000037e0| 54 49 4f 4e 0a 58 0a 58 | 20 20 53 6f 72 74 73 20 |TION.X.X| Sorts |
|000037f0| 62 79 20 69 6e 73 65 72 | 74 69 6e 67 20 65 61 63 |by inser|ting eac|
|00003800| 68 20 73 75 63 63 65 73 | 73 69 76 65 20 72 65 63 |h succes|sive rec|
|00003810| 6f 72 64 20 69 6e 74 6f | 20 69 74 73 20 70 72 6f |ord into| its pro|
|00003820| 70 65 72 20 70 6c 61 63 | 65 20 69 6e 0a 58 20 20 |per plac|e in.X |
|00003830| 74 68 65 20 70 72 65 63 | 65 65 64 69 6e 67 2c 20 |the prec|eeding, |
|00003840| 61 6c 72 65 61 64 79 20 | 73 6f 72 74 65 64 20 72 |already |sorted r|
|00003850| 65 63 6f 72 64 73 2e 20 | 20 20 50 65 72 66 6f 72 |ecords. | Perfor|
|00003860| 6d 20 61 20 62 69 6e 61 | 72 79 20 73 65 61 72 63 |m a bina|ry searc|
|00003870| 68 20 6f 6e 0a 58 20 20 | 74 68 65 20 70 72 65 63 |h on.X |the prec|
|00003880| 65 65 64 69 6e 67 20 72 | 65 63 6f 72 64 73 20 74 |eeding r|ecords t|
|00003890| 6f 20 66 69 6e 64 20 77 | 68 65 72 65 20 74 6f 20 |o find w|here to |
|000038a0| 69 6e 73 65 72 74 20 74 | 68 65 20 63 75 72 72 65 |insert t|he curre|
|000038b0| 6e 74 20 72 65 63 6f 72 | 64 2c 0a 58 20 20 74 68 |nt recor|d,.X th|
|000038c0| 65 6e 20 73 68 69 66 74 | 20 61 6c 6c 20 74 68 65 |en shift| all the|
|000038d0| 20 72 65 63 6f 72 64 73 | 20 6f 76 65 72 20 74 6f | records| over to|
|000038e0| 20 6d 61 6b 65 20 72 6f | 6f 6d 20 69 6e 20 74 68 | make ro|om in th|
|000038f0| 65 20 72 69 67 68 74 20 | 70 6c 61 63 65 2e 0a 58 |e right |place..X|
|00003900| 0a 58 41 55 54 48 4f 52 | 53 48 49 50 0a 58 0a 58 |.XAUTHOR|SHIP.X.X|
|00003910| 20 20 54 68 69 73 20 69 | 73 20 70 72 6f 70 65 72 | This i|s proper|
|00003920| 6c 79 20 63 61 6c 6c 65 | 64 20 74 68 65 20 62 69 |ly calle|d the bi|
|00003930| 6e 61 72 79 20 69 6e 73 | 65 72 74 69 6f 6e 20 73 |nary ins|ertion s|
|00003940| 6f 72 74 20 61 6e 64 20 | 63 72 65 64 69 74 20 69 |ort and |credit i|
|00003950| 73 0a 58 20 20 67 69 76 | 65 6e 20 66 6f 72 20 66 |s.X giv|en for f|
|00003960| 69 72 73 74 20 70 75 62 | 6c 69 63 61 74 69 6f 6e |irst pub|lication|
|00003970| 20 74 6f 20 4a 6f 68 6e | 20 4d 61 75 63 68 6c 79 | to John| Mauchly|
|00003980| 2c 20 31 39 34 36 2e 0a | 58 0a 58 52 45 46 45 52 |, 1946..|X.XREFER|
|00003990| 45 4e 43 45 53 0a 58 0a | 58 20 20 4b 6e 75 74 68 |ENCES.X.|X Knuth|
|000039a0| 2c 20 41 72 74 20 6f 66 | 20 43 6f 6d 70 75 74 65 |, Art of| Compute|
|000039b0| 72 20 50 72 6f 67 72 61 | 6d 6d 69 6e 67 20 56 6f |r Progra|mming Vo|
|000039c0| 6c 20 33 2c 20 70 61 67 | 65 20 38 33 2e 0a 58 0a |l 3, pag|e 83..X.|
|000039d0| 58 43 4f 4d 50 4c 45 58 | 49 54 59 0a 58 0a 58 20 |XCOMPLEX|ITY.X.X |
|000039e0| 20 4f 28 6e 20 6c 6f 67 | 20 6e 29 20 63 6f 6d 70 | O(n log| n) comp|
|000039f0| 61 72 69 73 6f 6e 73 20 | 0a 58 20 20 4f 28 30 2e |arisons |.X O(0.|
|00003a00| 32 35 20 2a 20 6e 5e 32 | 29 20 6d 65 6d 6f 72 79 |25 * n^2|) memory|
|00003a10| 20 6f 70 65 72 61 74 69 | 6f 6e 73 0a 58 20 20 49 | operati|ons.X I|
|00003a20| 74 65 72 61 74 69 76 65 | 2e 0a 58 0a 58 43 4f 50 |terative|..X.XCOP|
|00003a30| 59 52 49 47 48 54 0a 58 | 0a 58 20 20 43 6f 70 79 |YRIGHT.X|.X Copy|
|00003a40| 72 69 67 68 74 20 31 39 | 39 32 20 4d 69 63 68 61 |right 19|92 Micha|
|00003a50| 65 6c 20 4c 65 65 2e 0a | 58 0a 58 20 20 28 31 29 |el Lee..|X.X (1)|
|00003a60| 20 50 65 72 6d 69 73 73 | 69 6f 6e 20 74 6f 20 75 | Permiss|ion to u|
|00003a70| 73 65 2c 20 63 6f 70 79 | 2c 20 64 69 73 74 72 69 |se, copy|, distri|
|00003a80| 62 75 74 65 2c 20 61 6e | 64 20 6d 61 6b 65 20 63 |bute, an|d make c|
|00003a90| 68 61 6e 67 65 73 20 69 | 73 20 67 72 61 6e 74 65 |hanges i|s grante|
|00003aa0| 64 0a 58 20 20 70 72 6f | 76 69 64 69 6e 67 20 74 |d.X pro|viding t|
|00003ab0| 68 61 74 20 28 61 29 20 | 74 68 61 74 20 79 6f 75 |hat (a) |that you|
|00003ac0| 20 64 6f 20 73 6f 20 77 | 69 74 68 6f 75 74 20 63 | do so w|ithout c|
|00003ad0| 68 61 72 67 69 6e 67 20 | 61 6e 79 6f 6e 65 20 61 |harging |anyone a|
|00003ae0| 20 66 65 65 20 61 6e 64 | 0a 58 20 20 28 62 29 20 | fee and|.X (b) |
|00003af0| 74 68 69 73 20 63 6f 70 | 79 72 69 67 68 74 20 6e |this cop|yright n|
|00003b00| 6f 74 69 63 65 20 6d 75 | 73 74 20 62 65 20 69 6e |otice mu|st be in|
|00003b10| 63 6c 75 64 65 64 20 76 | 65 72 62 61 74 69 6d 20 |cluded v|erbatim |
|00003b20| 69 6e 20 61 6c 6c 20 63 | 6f 70 69 65 73 20 61 6e |in all c|opies an|
|00003b30| 64 20 0a 58 20 20 64 69 | 73 74 72 69 62 75 74 69 |d .X di|stributi|
|00003b40| 6f 6e 73 2e 20 20 0a 58 | 0a 58 20 20 28 32 29 20 |ons. .X|.X (2) |
|00003b50| 54 68 65 72 65 20 69 73 | 20 6e 6f 20 77 61 72 72 |There is| no warr|
|00003b60| 61 6e 74 79 20 66 6f 72 | 20 74 68 69 73 20 70 72 |anty for| this pr|
|00003b70| 6f 67 72 61 6d 2c 20 74 | 6f 20 74 68 65 20 65 78 |ogram, t|o the ex|
|00003b80| 74 65 6e 74 20 70 65 72 | 6d 69 74 74 65 64 20 62 |tent per|mitted b|
|00003b90| 79 0a 58 20 20 61 70 70 | 6c 69 63 61 62 6c 65 20 |y.X app|licable |
|00003ba0| 6c 61 77 2e 20 20 54 68 | 69 73 20 70 72 6f 67 72 |law. Th|is progr|
|00003bb0| 61 6d 20 69 73 20 70 72 | 6f 76 69 64 65 64 20 22 |am is pr|ovided "|
|00003bc0| 41 53 20 49 53 22 20 77 | 69 74 68 6f 75 74 20 77 |AS IS" w|ithout w|
|00003bd0| 61 72 72 61 6e 74 79 20 | 6f 66 0a 58 20 20 61 6e |arranty |of.X an|
|00003be0| 79 20 6b 69 6e 64 2c 20 | 65 69 74 68 65 72 20 65 |y kind, |either e|
|00003bf0| 78 70 72 65 73 73 65 64 | 20 6f 72 20 69 6d 70 6c |xpressed| or impl|
|00003c00| 69 65 64 2c 20 69 6e 63 | 6c 75 64 69 6e 67 2c 20 |ied, inc|luding, |
|00003c10| 62 75 74 20 6e 6f 74 20 | 6c 69 6d 69 74 65 64 20 |but not |limited |
|00003c20| 74 6f 2c 0a 58 20 20 74 | 68 65 20 69 6d 70 6c 69 |to,.X t|he impli|
|00003c30| 65 64 20 77 61 72 72 61 | 6e 74 69 65 73 20 6f 66 |ed warra|nties of|
|00003c40| 20 6d 65 72 63 68 61 6e | 74 61 62 69 6c 69 74 79 | merchan|tability|
|00003c50| 20 61 6e 64 20 66 69 74 | 6e 65 73 73 20 66 6f 72 | and fit|ness for|
|00003c60| 20 61 20 70 61 72 74 69 | 63 75 6c 61 72 20 0a 58 | a parti|cular .X|
|00003c70| 20 20 70 75 72 70 6f 73 | 65 2e 20 20 54 68 65 20 | purpos|e. The |
|00003c80| 65 6e 74 69 72 65 20 72 | 69 73 6b 20 61 73 20 74 |entire r|isk as t|
|00003c90| 6f 20 74 68 65 20 71 75 | 61 6c 69 74 79 20 61 6e |o the qu|ality an|
|00003ca0| 64 20 70 65 72 66 6f 72 | 6d 61 6e 63 65 20 6f 66 |d perfor|mance of|
|00003cb0| 20 74 68 69 73 20 0a 58 | 20 20 70 72 6f 67 72 61 | this .X| progra|
|00003cc0| 6d 20 69 73 20 77 69 74 | 68 20 74 68 65 20 75 73 |m is wit|h the us|
|00003cd0| 65 72 2e 20 20 53 68 6f | 75 6c 64 20 74 68 69 73 |er. Sho|uld this|
|00003ce0| 20 70 72 6f 67 72 61 6d | 20 70 72 6f 76 65 20 64 | program| prove d|
|00003cf0| 65 66 65 63 74 69 76 65 | 2c 20 74 68 65 20 0a 58 |efective|, the .X|
|00003d00| 20 20 75 73 65 72 20 61 | 73 73 75 6d 65 73 20 74 | user a|ssumes t|
|00003d10| 68 65 20 63 6f 73 74 20 | 6f 66 20 61 6c 6c 20 6e |he cost |of all n|
|00003d20| 65 63 65 73 73 61 72 79 | 20 73 65 72 76 69 63 69 |ecessary| servici|
|00003d30| 6e 67 2c 20 72 65 70 61 | 69 72 20 6f 72 20 63 6f |ng, repa|ir or co|
|00003d40| 72 72 65 63 74 69 6f 6e | 2e 0a 58 0a 58 20 20 28 |rrection|..X.X (|
|00003d50| 33 29 20 49 6e 20 6e 6f | 20 65 76 65 6e 74 20 75 |3) In no| event u|
|00003d60| 6e 6c 65 73 73 20 72 65 | 71 75 69 72 65 64 20 62 |nless re|quired b|
|00003d70| 79 20 61 70 70 6c 69 63 | 61 62 6c 65 20 6c 61 77 |y applic|able law|
|00003d80| 20 77 69 6c 6c 20 74 68 | 65 20 63 6f 70 79 72 69 | will th|e copyri|
|00003d90| 67 68 74 0a 58 20 20 68 | 6f 6c 64 65 72 20 62 65 |ght.X h|older be|
|00003da0| 20 6c 69 61 62 6c 65 20 | 74 6f 20 74 68 65 20 75 | liable |to the u|
|00003db0| 73 65 72 20 66 6f 72 20 | 64 61 6d 61 67 65 73 2c |ser for |damages,|
|00003dc0| 20 69 6e 63 6c 75 64 69 | 6e 67 20 61 6e 79 20 67 | includi|ng any g|
|00003dd0| 65 6e 65 72 61 6c 2c 0a | 58 20 20 73 70 65 63 69 |eneral,.|X speci|
|00003de0| 61 6c 2c 20 69 6e 63 69 | 64 65 6e 74 61 6c 20 6f |al, inci|dental o|
|00003df0| 72 20 63 6f 6e 73 65 71 | 75 65 6e 74 69 61 6c 20 |r conseq|uential |
|00003e00| 64 61 6d 61 67 65 73 20 | 61 72 69 73 69 6e 67 20 |damages |arising |
|00003e10| 6f 75 74 20 6f 66 20 74 | 68 65 20 75 73 65 0a 58 |out of t|he use.X|
|00003e20| 20 20 6f 72 20 69 6e 61 | 62 69 6c 69 74 79 20 74 | or ina|bility t|
|00003e30| 6f 20 75 73 65 20 74 68 | 69 73 20 70 72 6f 67 72 |o use th|is progr|
|00003e40| 61 6d 20 28 69 6e 63 6c | 75 64 69 6e 67 20 62 75 |am (incl|uding bu|
|00003e50| 74 20 6e 6f 74 20 6c 69 | 6d 69 74 65 64 20 74 6f |t not li|mited to|
|00003e60| 20 6c 6f 73 73 20 6f 66 | 0a 58 20 20 64 61 74 61 | loss of|.X data|
|00003e70| 20 6f 72 20 64 61 74 61 | 20 62 65 69 6e 67 20 72 | or data| being r|
|00003e80| 65 6e 64 65 72 65 64 20 | 69 6e 61 63 63 75 72 61 |endered |inaccura|
|00003e90| 74 65 20 6f 72 20 6c 6f | 73 73 65 73 20 73 75 73 |te or lo|sses sus|
|00003ea0| 74 61 69 6e 65 64 20 62 | 79 20 74 68 65 0a 58 20 |tained b|y the.X |
|00003eb0| 20 75 73 65 72 20 6f 72 | 20 74 68 69 72 64 20 70 | user or| third p|
|00003ec0| 61 72 74 69 65 73 20 6f | 72 20 61 20 66 61 69 6c |arties o|r a fail|
|00003ed0| 75 72 65 20 6f 66 20 74 | 68 69 73 20 70 72 6f 67 |ure of t|his prog|
|00003ee0| 72 61 6d 20 74 6f 20 6f | 70 65 72 61 74 65 20 77 |ram to o|perate w|
|00003ef0| 69 74 68 20 61 6e 79 0a | 58 20 20 6f 74 68 65 72 |ith any.|X other|
|00003f00| 20 70 72 6f 67 72 61 6d | 73 29 2c 20 65 76 65 6e | program|s), even|
|00003f10| 20 69 66 20 73 75 63 68 | 20 68 6f 6c 64 65 72 20 | if such| holder |
|00003f20| 6f 72 20 74 68 69 72 64 | 20 70 61 72 74 79 20 68 |or third| party h|
|00003f30| 61 73 20 62 65 65 6e 20 | 61 64 76 69 73 65 64 0a |as been |advised.|
|00003f40| 58 20 20 6f 66 20 74 68 | 65 20 70 6f 73 73 69 62 |X of th|e possib|
|00003f50| 69 6c 69 74 79 20 6f 66 | 20 73 75 63 68 20 64 61 |ility of| such da|
|00003f60| 6d 61 67 65 73 2e 0a 58 | 0a 58 20 20 28 34 29 20 |mages..X|.X (4) |
|00003f70| 4f 62 6a 65 63 74 20 63 | 6f 64 65 20 70 72 6f 64 |Object c|ode prod|
|00003f80| 75 63 65 64 20 62 79 20 | 61 20 63 6f 6d 70 69 6c |uced by |a compil|
|00003f90| 65 72 20 66 72 6f 6d 20 | 74 68 69 73 20 63 6f 64 |er from |this cod|
|00003fa0| 65 20 6d 61 79 20 62 65 | 20 0a 58 20 20 69 6e 63 |e may be| .X inc|
|00003fb0| 6f 72 70 6f 72 61 74 65 | 64 20 69 6e 74 6f 20 63 |orporate|d into c|
|00003fc0| 6f 6d 6d 65 72 63 69 61 | 6c 20 70 72 6f 64 75 63 |ommercia|l produc|
|00003fd0| 74 73 20 77 69 74 68 6f | 75 74 20 62 65 69 6e 67 |ts witho|ut being|
|00003fe0| 20 73 75 62 6a 65 63 74 | 20 74 6f 20 0a 58 20 20 | subject| to .X |
|00003ff0| 72 65 73 74 72 69 63 74 | 69 6f 6e 73 20 28 31 29 |restrict|ions (1)|
|00004000| 28 61 29 20 6f 72 20 28 | 31 29 28 62 29 2e 0a 58 |(a) or (|1)(b)..X|
|00004010| 0a 58 2a 2f 0a 58 0a 58 | 23 69 6e 63 6c 75 64 65 |.X*/.X.X|#include|
|00004020| 20 3c 73 74 64 69 6f 2e | 68 3e 0a 58 23 69 6e 63 | <stdio.|h>.X#inc|
|00004030| 6c 75 64 65 20 3c 6d 61 | 6c 6c 6f 63 2e 68 3e 0a |lude <ma|lloc.h>.|
|00004040| 58 23 69 6e 63 6c 75 64 | 65 20 3c 6d 65 6d 6f 72 |X#includ|e <memor|
|00004050| 79 2e 68 3e 0a 58 23 69 | 6e 63 6c 75 64 65 20 3c |y.h>.X#i|nclude <|
|00004060| 73 74 72 69 6e 67 2e 68 | 3e 0a 58 23 69 6e 63 6c |string.h|>.X#incl|
|00004070| 75 64 65 20 3c 61 73 73 | 65 72 74 2e 68 3e 0a 58 |ude <ass|ert.h>.X|
|00004080| 0a 58 23 69 6e 63 6c 75 | 64 65 20 22 73 6f 72 74 |.X#inclu|de "sort|
|00004090| 69 6e 67 2e 68 22 0a 58 | 0a 58 69 6e 74 20 69 6e |ing.h".X|.Xint in|
|000040a0| 73 65 72 74 69 6f 6e 5f | 73 6f 72 74 28 62 61 73 |sertion_|sort(bas|
|000040b0| 65 2c 20 6e 65 6c 65 6d | 2c 20 77 69 64 74 68 2c |e, nelem|, width,|
|000040c0| 20 63 6d 70 72 5f 66 75 | 6e 63 29 0a 58 20 20 63 | cmpr_fu|nc).X c|
|000040d0| 68 61 72 20 2a 20 62 61 | 73 65 3b 0a 58 20 20 69 |har * ba|se;.X i|
|000040e0| 6e 74 20 6e 65 6c 65 6d | 3b 0a 58 20 20 69 6e 74 |nt nelem|;.X int|
|000040f0| 20 77 69 64 74 68 3b 0a | 58 20 20 69 6e 74 20 28 | width;.|X int (|
|00004100| 2a 63 6d 70 72 5f 66 75 | 6e 63 29 28 29 3b 0a 58 |*cmpr_fu|nc)();.X|
|00004110| 7b 0a 58 20 20 69 6e 74 | 20 69 2c 20 74 6f 70 2c |{.X int| i, top,|
|00004120| 20 6d 69 64 64 6c 65 2c | 20 62 6f 74 74 6f 6d 3b | middle,| bottom;|
|00004130| 0a 58 20 20 69 6e 74 20 | 66 6f 75 6e 64 2c 20 74 |.X int |found, t|
|00004140| 65 73 74 3b 0a 58 20 20 | 63 68 61 72 20 2a 20 74 |est;.X |char * t|
|00004150| 65 6d 70 3b 0a 58 0a 58 | 20 20 74 65 6d 70 20 3d |emp;.X.X| temp =|
|00004160| 20 6d 61 6c 6c 6f 63 28 | 77 69 64 74 68 29 3b 0a | malloc(|width);.|
|00004170| 58 20 20 61 73 73 65 72 | 74 28 74 65 6d 70 20 21 |X asser|t(temp !|
|00004180| 3d 20 4e 55 4c 4c 29 3b | 0a 58 0a 58 20 20 66 6f |= NULL);|.X.X fo|
|00004190| 72 20 28 69 20 3d 20 31 | 3b 20 69 20 3c 20 6e 65 |r (i = 1|; i < ne|
|000041a0| 6c 65 6d 3b 20 69 2b 2b | 29 0a 58 20 20 7b 0a 58 |lem; i++|).X {.X|
|000041b0| 20 20 20 20 2f 2a 20 62 | 69 6e 61 72 79 20 73 65 | /* b|inary se|
|000041c0| 61 72 63 68 20 6c 6f 6f | 6b 69 6e 67 20 66 6f 72 |arch loo|king for|
|000041d0| 20 70 6c 61 63 65 20 62 | 65 74 77 65 65 6e 20 62 | place b|etween b|
|000041e0| 61 73 65 5b 30 5d 20 61 | 6e 64 20 62 61 73 65 5b |ase[0] a|nd base[|
|000041f0| 69 2d 31 5d 20 77 68 65 | 72 65 0a 58 20 20 20 20 |i-1] whe|re.X |
|00004200| 20 20 20 79 6f 75 20 63 | 61 6e 20 69 6e 73 65 72 | you c|an inser|
|00004210| 74 20 62 61 73 65 5b 69 | 5d 20 69 6e 74 6f 20 69 |t base[i|] into i|
|00004220| 6e 20 6f 72 64 65 72 2e | 20 2a 2f 0a 58 0a 58 20 |n order.| */.X.X |
|00004230| 20 20 20 62 6f 74 74 6f | 6d 20 3d 20 30 3b 0a 58 | botto|m = 0;.X|
|00004240| 20 20 20 20 74 6f 70 20 | 3d 20 69 2d 31 3b 0a 58 | top |= i-1;.X|
|00004250| 20 20 20 20 6d 69 64 64 | 6c 65 20 3d 20 30 3b 0a | midd|le = 0;.|
|00004260| 58 20 20 20 20 66 6f 75 | 6e 64 20 3d 20 30 3b 0a |X fou|nd = 0;.|
|00004270| 58 0a 58 20 20 20 20 77 | 68 69 6c 65 20 28 74 6f |X.X w|hile (to|
|00004280| 70 20 3e 3d 20 62 6f 74 | 74 6f 6d 20 26 26 20 21 |p >= bot|tom && !|
|00004290| 20 66 6f 75 6e 64 29 0a | 58 20 20 20 20 7b 0a 58 | found).|X {.X|
|000042a0| 20 20 20 20 20 20 6d 69 | 64 64 6c 65 20 3d 20 28 | mi|ddle = (|
|000042b0| 74 6f 70 2b 62 6f 74 74 | 6f 6d 29 20 2f 20 32 3b |top+bott|om) / 2;|
|000042c0| 0a 58 20 20 20 20 20 20 | 74 65 73 74 20 3d 20 28 |.X |test = (|
|000042d0| 2a 63 6d 70 72 5f 66 75 | 6e 63 29 28 62 61 73 65 |*cmpr_fu|nc)(base|
|000042e0| 2b 6d 69 64 64 6c 65 2a | 77 69 64 74 68 2c 20 62 |+middle*|width, b|
|000042f0| 61 73 65 2b 69 2a 77 69 | 64 74 68 29 3b 0a 58 0a |ase+i*wi|dth);.X.|
|00004300| 58 20 20 20 20 20 20 69 | 66 20 28 74 65 73 74 20 |X i|f (test |
|00004310| 3e 20 30 29 0a 58 20 20 | 20 20 20 20 20 20 74 6f |> 0).X | to|
|00004320| 70 20 3d 20 6d 69 64 64 | 6c 65 20 2d 20 31 3b 0a |p = midd|le - 1;.|
|00004330| 58 20 20 20 20 20 20 65 | 6c 73 65 20 69 66 20 28 |X e|lse if (|
|00004340| 74 65 73 74 20 3c 20 30 | 29 0a 58 20 20 20 20 20 |test < 0|).X |
|00004350| 20 7b 0a 58 20 20 20 20 | 20 20 20 20 6d 69 64 64 | {.X | midd|
|00004360| 6c 65 20 2b 2b 3b 0a 58 | 20 20 20 20 20 20 20 20 |le ++;.X| |
|00004370| 62 6f 74 74 6f 6d 20 3d | 20 6d 69 64 64 6c 65 3b |bottom =| middle;|
|00004380| 0a 58 20 20 20 20 20 20 | 7d 0a 58 20 20 20 20 20 |.X |}.X |
|00004390| 20 65 6c 73 65 0a 58 20 | 20 20 20 20 20 7b 0a 58 | else.X | {.X|
|000043a0| 20 20 20 20 20 20 20 20 | 6d 69 64 64 6c 65 20 2b | |middle +|
|000043b0| 2b 3b 0a 58 20 20 20 20 | 20 20 20 20 66 6f 75 6e |+;.X | foun|
|000043c0| 64 20 3d 20 31 3b 0a 58 | 20 20 20 20 20 20 7d 0a |d = 1;.X| }.|
|000043d0| 58 20 20 20 20 7d 0a 58 | 0a 58 20 20 20 20 2f 2a |X }.X|.X /*|
|000043e0| 20 6d 61 6b 65 20 72 6f | 6f 6d 20 61 74 20 62 61 | make ro|om at ba|
|000043f0| 73 65 5b 6d 69 64 64 6c | 65 5d 20 66 6f 72 20 62 |se[middl|e] for b|
|00004400| 61 73 65 5b 69 5d 20 2a | 2f 0a 58 0a 58 20 20 20 |ase[i] *|/.X.X |
|00004410| 20 69 66 20 28 69 20 21 | 3d 20 6d 69 64 64 6c 65 | if (i !|= middle|
|00004420| 29 0a 58 20 20 20 20 7b | 0a 58 20 20 20 20 20 20 |).X {|.X |
|00004430| 6d 65 6d 63 70 79 28 74 | 65 6d 70 2c 20 62 61 73 |memcpy(t|emp, bas|
|00004440| 65 2b 69 2a 77 69 64 74 | 68 2c 20 77 69 64 74 68 |e+i*widt|h, width|
|00004450| 29 3b 0a 58 20 20 20 20 | 20 20 6d 65 6d 6d 6f 76 |);.X | memmov|
|00004460| 65 28 62 61 73 65 2b 6d | 69 64 64 6c 65 2a 77 69 |e(base+m|iddle*wi|
|00004470| 64 74 68 2b 77 69 64 74 | 68 2c 20 62 61 73 65 2b |dth+widt|h, base+|
|00004480| 6d 69 64 64 6c 65 2a 77 | 69 64 74 68 2c 20 28 69 |middle*w|idth, (i|
|00004490| 2d 6d 69 64 64 6c 65 29 | 2a 77 69 64 74 68 29 3b |-middle)|*width);|
|000044a0| 0a 58 20 20 20 20 20 20 | 6d 65 6d 63 70 79 28 62 |.X |memcpy(b|
|000044b0| 61 73 65 2b 6d 69 64 64 | 6c 65 2a 77 69 64 74 68 |ase+midd|le*width|
|000044c0| 2c 20 74 65 6d 70 2c 20 | 77 69 64 74 68 29 3b 0a |, temp, |width);.|
|000044d0| 58 20 20 20 20 7d 0a 58 | 20 20 7d 0a 58 0a 58 20 |X }.X| }.X.X |
|000044e0| 20 69 66 20 28 74 65 6d | 70 20 21 3d 20 4e 55 4c | if (tem|p != NUL|
|000044f0| 4c 29 20 66 72 65 65 28 | 74 65 6d 70 29 3b 0a 58 |L) free(|temp);.X|
|00004500| 0a 58 20 20 72 65 74 75 | 72 6e 20 30 3b 0a 58 0a |.X retu|rn 0;.X.|
|00004510| 58 7d 0a 45 4e 44 5f 4f | 46 5f 46 49 4c 45 0a 20 |X}.END_O|F_FILE. |
|00004520| 20 69 66 20 74 65 73 74 | 20 33 32 39 38 20 2d 6e | if test| 3298 -n|
|00004530| 65 20 60 77 63 20 2d 63 | 20 3c 27 69 6e 73 65 72 |e `wc -c| <'inser|
|00004540| 74 5f 73 6f 72 74 2e 63 | 27 60 3b 20 74 68 65 6e |t_sort.c|'`; then|
|00004550| 0a 20 20 20 20 65 63 68 | 6f 20 73 68 61 72 3a 20 |. ech|o shar: |
|00004560| 5c 22 27 69 6e 73 65 72 | 74 5f 73 6f 72 74 2e 63 |\"'inser|t_sort.c|
|00004570| 27 5c 22 20 75 6e 70 61 | 63 6b 65 64 20 77 69 74 |'\" unpa|cked wit|
|00004580| 68 20 77 72 6f 6e 67 20 | 73 69 7a 65 21 0a 20 20 |h wrong |size!. |
|00004590| 66 69 0a 20 20 23 20 65 | 6e 64 20 6f 66 20 27 69 |fi. # e|nd of 'i|
|000045a0| 6e 73 65 72 74 5f 73 6f | 72 74 2e 63 27 0a 66 69 |nsert_so|rt.c'.fi|
|000045b0| 0a 69 66 20 74 65 73 74 | 20 2d 66 20 27 73 68 65 |.if test| -f 'she|
|000045c0| 6c 6c 5f 73 6f 72 74 2e | 63 27 20 2d 61 20 22 24 |ll_sort.|c' -a "$|
|000045d0| 7b 31 7d 22 20 21 3d 20 | 22 2d 63 22 20 3b 20 74 |{1}" != |"-c" ; t|
|000045e0| 68 65 6e 20 0a 20 20 65 | 63 68 6f 20 73 68 61 72 |hen . e|cho shar|
|000045f0| 3a 20 57 69 6c 6c 20 6e | 6f 74 20 63 6c 6f 62 62 |: Will n|ot clobb|
|00004600| 65 72 20 65 78 69 73 74 | 69 6e 67 20 66 69 6c 65 |er exist|ing file|
|00004610| 20 5c 22 27 73 68 65 6c | 6c 5f 73 6f 72 74 2e 63 | \"'shel|l_sort.c|
|00004620| 27 5c 22 0a 65 6c 73 65 | 0a 20 20 65 63 68 6f 20 |'\".else|. echo |
|00004630| 73 68 61 72 3a 20 45 78 | 74 72 61 63 74 69 6e 67 |shar: Ex|tracting|
|00004640| 20 5c 22 27 73 68 65 6c | 6c 5f 73 6f 72 74 2e 63 | \"'shel|l_sort.c|
|00004650| 27 5c 22 20 5c 28 32 36 | 36 38 20 63 68 61 72 61 |'\" \(26|68 chara|
|00004660| 63 74 65 72 73 5c 29 0a | 20 20 73 65 64 20 22 73 |cters\).| sed "s|
|00004670| 2f 5e 58 2f 2f 22 20 3e | 27 73 68 65 6c 6c 5f 73 |/^X//" >|'shell_s|
|00004680| 6f 72 74 2e 63 27 20 3c | 3c 27 45 4e 44 5f 4f 46 |ort.c' <|<'END_OF|
|00004690| 5f 46 49 4c 45 27 0a 58 | 0a 58 2f 2a 0a 58 0a 58 |_FILE'.X|.X/*.X.X|
|000046a0| 4e 41 4d 45 0a 58 20 20 | 73 68 65 6c 6c 20 73 6f |NAME.X |shell so|
|000046b0| 72 74 20 0a 58 0a 58 44 | 45 53 43 52 49 50 54 49 |rt .X.XD|ESCRIPTI|
|000046c0| 4f 4e 0a 58 0a 58 20 20 | 41 6e 20 65 78 68 61 6e |ON.X.X |An exhan|
|000046d0| 67 65 20 73 6f 72 74 20 | 61 6c 67 6f 72 69 74 68 |ge sort |algorith|
|000046e0| 6d 20 77 68 69 63 68 20 | 65 78 63 68 61 6e 67 65 |m which |exchange|
|000046f0| 73 20 6f 76 65 72 20 6c | 61 72 67 65 72 20 64 69 |s over l|arger di|
|00004700| 73 74 61 6e 63 65 73 0a | 58 20 20 74 68 61 6e 20 |stances.|X than |
|00004710| 62 75 62 62 6c 65 20 73 | 6f 72 74 2c 20 74 68 75 |bubble s|ort, thu|
|00004720| 73 20 72 65 64 75 63 69 | 6e 67 20 74 68 65 20 6e |s reduci|ng the n|
|00004730| 75 6d 62 65 72 20 6f 66 | 20 65 78 63 68 61 6e 67 |umber of| exchang|
|00004740| 65 73 20 6e 65 65 64 65 | 64 2e 0a 58 0a 58 41 55 |es neede|d..X.XAU|
|00004750| 54 48 4f 52 53 48 49 50 | 0a 58 0a 58 20 20 44 2e |THORSHIP|.X.X D.|
|00004760| 20 4c 2e 20 53 68 65 6c | 6c 0a 58 0a 58 52 45 46 | L. Shel|l.X.XREF|
|00004770| 45 52 45 4e 43 45 53 0a | 58 0a 58 20 20 44 2e 20 |ERENCES.|X.X D. |
|00004780| 4c 2e 20 53 68 65 6c 6c | 2c 20 43 41 43 4d 20 32 |L. Shell|, CACM 2|
|00004790| 2c 20 4a 75 6c 79 20 31 | 39 35 39 0a 58 20 20 4b |, July 1|959.X K|
|000047a0| 65 72 6e 69 67 68 61 6e | 20 26 20 52 69 74 63 68 |ernighan| & Ritch|
|000047b0| 69 65 2c 20 43 20 50 72 | 6f 67 72 61 6d 6d 69 6e |ie, C Pr|ogrammin|
|000047c0| 67 20 4c 61 6e 67 75 61 | 67 65 2c 20 53 65 63 6f |g Langua|ge, Seco|
|000047d0| 6e 64 20 45 64 69 74 69 | 6f 6e 2c 20 70 67 20 36 |nd Editi|on, pg 6|
|000047e0| 32 0a 58 20 20 4b 6e 75 | 74 68 2c 20 41 72 74 20 |2.X Knu|th, Art |
|000047f0| 6f 66 20 43 6f 6d 70 75 | 74 65 72 20 50 72 6f 67 |of Compu|ter Prog|
|00004800| 72 61 6d 6d 69 6e 67 20 | 56 6f 6c 20 33 2c 20 70 |ramming |Vol 3, p|
|00004810| 67 20 38 34 2d 39 35 0a | 58 0a 58 43 4f 4d 50 4c |g 84-95.|X.XCOMPL|
|00004820| 45 58 49 54 59 0a 58 0a | 58 20 20 49 27 6d 20 6e |EXITY.X.|X I'm n|
|00004830| 6f 74 20 65 78 61 63 74 | 6c 79 20 73 75 72 65 2c |ot exact|ly sure,|
|00004840| 20 62 75 74 20 49 20 74 | 68 69 6e 6b 20 69 74 27 | but I t|hink it'|
|00004850| 73 20 4f 28 4e 5e 31 2e | 35 29 20 0a 58 20 20 49 |s O(N^1.|5) .X I|
|00004860| 74 65 72 61 74 69 76 65 | 2e 0a 58 0a 58 43 4f 50 |terative|..X.XCOP|
|00004870| 59 52 49 47 48 54 0a 58 | 0a 58 20 20 43 6f 70 79 |YRIGHT.X|.X Copy|
|00004880| 72 69 67 68 74 20 31 39 | 39 32 20 4d 69 63 68 61 |right 19|92 Micha|
|00004890| 65 6c 20 4c 65 65 2e 0a | 58 0a 58 20 20 28 31 29 |el Lee..|X.X (1)|
|000048a0| 20 50 65 72 6d 69 73 73 | 69 6f 6e 20 74 6f 20 75 | Permiss|ion to u|
|000048b0| 73 65 2c 20 63 6f 70 79 | 2c 20 64 69 73 74 72 69 |se, copy|, distri|
|000048c0| 62 75 74 65 2c 20 61 6e | 64 20 6d 61 6b 65 20 63 |bute, an|d make c|
|000048d0| 68 61 6e 67 65 73 20 69 | 73 20 67 72 61 6e 74 65 |hanges i|s grante|
|000048e0| 64 0a 58 20 20 70 72 6f | 76 69 64 69 6e 67 20 74 |d.X pro|viding t|
|000048f0| 68 61 74 20 28 61 29 20 | 74 68 61 74 20 79 6f 75 |hat (a) |that you|
|00004900| 20 64 6f 20 73 6f 20 77 | 69 74 68 6f 75 74 20 63 | do so w|ithout c|
|00004910| 68 61 72 67 69 6e 67 20 | 61 6e 79 6f 6e 65 20 61 |harging |anyone a|
|00004920| 20 66 65 65 20 61 6e 64 | 0a 58 20 20 28 62 29 20 | fee and|.X (b) |
|00004930| 74 68 69 73 20 63 6f 70 | 79 72 69 67 68 74 20 6e |this cop|yright n|
|00004940| 6f 74 69 63 65 20 6d 75 | 73 74 20 62 65 20 69 6e |otice mu|st be in|
|00004950| 63 6c 75 64 65 64 20 76 | 65 72 62 61 74 69 6d 20 |cluded v|erbatim |
|00004960| 69 6e 20 61 6c 6c 20 63 | 6f 70 69 65 73 20 61 6e |in all c|opies an|
|00004970| 64 20 0a 58 20 20 64 69 | 73 74 72 69 62 75 74 69 |d .X di|stributi|
|00004980| 6f 6e 73 2e 20 20 0a 58 | 0a 58 20 20 28 32 29 20 |ons. .X|.X (2) |
|00004990| 54 68 65 72 65 20 69 73 | 20 6e 6f 20 77 61 72 72 |There is| no warr|
|000049a0| 61 6e 74 79 20 66 6f 72 | 20 74 68 69 73 20 70 72 |anty for| this pr|
|000049b0| 6f 67 72 61 6d 2c 20 74 | 6f 20 74 68 65 20 65 78 |ogram, t|o the ex|
|000049c0| 74 65 6e 74 20 70 65 72 | 6d 69 74 74 65 64 20 62 |tent per|mitted b|
|000049d0| 79 0a 58 20 20 61 70 70 | 6c 69 63 61 62 6c 65 20 |y.X app|licable |
|000049e0| 6c 61 77 2e 20 20 54 68 | 69 73 20 70 72 6f 67 72 |law. Th|is progr|
|000049f0| 61 6d 20 69 73 20 70 72 | 6f 76 69 64 65 64 20 22 |am is pr|ovided "|
|00004a00| 41 53 20 49 53 22 20 77 | 69 74 68 6f 75 74 20 77 |AS IS" w|ithout w|
|00004a10| 61 72 72 61 6e 74 79 20 | 6f 66 0a 58 20 20 61 6e |arranty |of.X an|
|00004a20| 79 20 6b 69 6e 64 2c 20 | 65 69 74 68 65 72 20 65 |y kind, |either e|
|00004a30| 78 70 72 65 73 73 65 64 | 20 6f 72 20 69 6d 70 6c |xpressed| or impl|
|00004a40| 69 65 64 2c 20 69 6e 63 | 6c 75 64 69 6e 67 2c 20 |ied, inc|luding, |
|00004a50| 62 75 74 20 6e 6f 74 20 | 6c 69 6d 69 74 65 64 20 |but not |limited |
|00004a60| 74 6f 2c 0a 58 20 20 74 | 68 65 20 69 6d 70 6c 69 |to,.X t|he impli|
|00004a70| 65 64 20 77 61 72 72 61 | 6e 74 69 65 73 20 6f 66 |ed warra|nties of|
|00004a80| 20 6d 65 72 63 68 61 6e | 74 61 62 69 6c 69 74 79 | merchan|tability|
|00004a90| 20 61 6e 64 20 66 69 74 | 6e 65 73 73 20 66 6f 72 | and fit|ness for|
|00004aa0| 20 61 20 70 61 72 74 69 | 63 75 6c 61 72 20 0a 58 | a parti|cular .X|
|00004ab0| 20 20 70 75 72 70 6f 73 | 65 2e 20 20 54 68 65 20 | purpos|e. The |
|00004ac0| 65 6e 74 69 72 65 20 72 | 69 73 6b 20 61 73 20 74 |entire r|isk as t|
|00004ad0| 6f 20 74 68 65 20 71 75 | 61 6c 69 74 79 20 61 6e |o the qu|ality an|
|00004ae0| 64 20 70 65 72 66 6f 72 | 6d 61 6e 63 65 20 6f 66 |d perfor|mance of|
|00004af0| 20 74 68 69 73 20 0a 58 | 20 20 70 72 6f 67 72 61 | this .X| progra|
|00004b00| 6d 20 69 73 20 77 69 74 | 68 20 74 68 65 20 75 73 |m is wit|h the us|
|00004b10| 65 72 2e 20 20 53 68 6f | 75 6c 64 20 74 68 69 73 |er. Sho|uld this|
|00004b20| 20 70 72 6f 67 72 61 6d | 20 70 72 6f 76 65 20 64 | program| prove d|
|00004b30| 65 66 65 63 74 69 76 65 | 2c 20 74 68 65 20 0a 58 |efective|, the .X|
|00004b40| 20 20 75 73 65 72 20 61 | 73 73 75 6d 65 73 20 74 | user a|ssumes t|
|00004b50| 68 65 20 63 6f 73 74 20 | 6f 66 20 61 6c 6c 20 6e |he cost |of all n|
|00004b60| 65 63 65 73 73 61 72 79 | 20 73 65 72 76 69 63 69 |ecessary| servici|
|00004b70| 6e 67 2c 20 72 65 70 61 | 69 72 20 6f 72 20 63 6f |ng, repa|ir or co|
|00004b80| 72 72 65 63 74 69 6f 6e | 2e 0a 58 0a 58 20 20 28 |rrection|..X.X (|
|00004b90| 33 29 20 49 6e 20 6e 6f | 20 65 76 65 6e 74 20 75 |3) In no| event u|
|00004ba0| 6e 6c 65 73 73 20 72 65 | 71 75 69 72 65 64 20 62 |nless re|quired b|
|00004bb0| 79 20 61 70 70 6c 69 63 | 61 62 6c 65 20 6c 61 77 |y applic|able law|
|00004bc0| 20 77 69 6c 6c 20 74 68 | 65 20 63 6f 70 79 72 69 | will th|e copyri|
|00004bd0| 67 68 74 0a 58 20 20 68 | 6f 6c 64 65 72 20 62 65 |ght.X h|older be|
|00004be0| 20 6c 69 61 62 6c 65 20 | 74 6f 20 74 68 65 20 75 | liable |to the u|
|00004bf0| 73 65 72 20 66 6f 72 20 | 64 61 6d 61 67 65 73 2c |ser for |damages,|
|00004c00| 20 69 6e 63 6c 75 64 69 | 6e 67 20 61 6e 79 20 67 | includi|ng any g|
|00004c10| 65 6e 65 72 61 6c 2c 0a | 58 20 20 73 70 65 63 69 |eneral,.|X speci|
|00004c20| 61 6c 2c 20 69 6e 63 69 | 64 65 6e 74 61 6c 20 6f |al, inci|dental o|
|00004c30| 72 20 63 6f 6e 73 65 71 | 75 65 6e 74 69 61 6c 20 |r conseq|uential |
|00004c40| 64 61 6d 61 67 65 73 20 | 61 72 69 73 69 6e 67 20 |damages |arising |
|00004c50| 6f 75 74 20 6f 66 20 74 | 68 65 20 75 73 65 0a 58 |out of t|he use.X|
|00004c60| 20 20 6f 72 20 69 6e 61 | 62 69 6c 69 74 79 20 74 | or ina|bility t|
|00004c70| 6f 20 75 73 65 20 74 68 | 69 73 20 70 72 6f 67 72 |o use th|is progr|
|00004c80| 61 6d 20 28 69 6e 63 6c | 75 64 69 6e 67 20 62 75 |am (incl|uding bu|
|00004c90| 74 20 6e 6f 74 20 6c 69 | 6d 69 74 65 64 20 74 6f |t not li|mited to|
|00004ca0| 20 6c 6f 73 73 20 6f 66 | 0a 58 20 20 64 61 74 61 | loss of|.X data|
|00004cb0| 20 6f 72 20 64 61 74 61 | 20 62 65 69 6e 67 20 72 | or data| being r|
|00004cc0| 65 6e 64 65 72 65 64 20 | 69 6e 61 63 63 75 72 61 |endered |inaccura|
|00004cd0| 74 65 20 6f 72 20 6c 6f | 73 73 65 73 20 73 75 73 |te or lo|sses sus|
|00004ce0| 74 61 69 6e 65 64 20 62 | 79 20 74 68 65 0a 58 20 |tained b|y the.X |
|00004cf0| 20 75 73 65 72 20 6f 72 | 20 74 68 69 72 64 20 70 | user or| third p|
|00004d00| 61 72 74 69 65 73 20 6f | 72 20 61 20 66 61 69 6c |arties o|r a fail|
|00004d10| 75 72 65 20 6f 66 20 74 | 68 69 73 20 70 72 6f 67 |ure of t|his prog|
|00004d20| 72 61 6d 20 74 6f 20 6f | 70 65 72 61 74 65 20 77 |ram to o|perate w|
|00004d30| 69 74 68 20 61 6e 79 0a | 58 20 20 6f 74 68 65 72 |ith any.|X other|
|00004d40| 20 70 72 6f 67 72 61 6d | 73 29 2c 20 65 76 65 6e | program|s), even|
|00004d50| 20 69 66 20 73 75 63 68 | 20 68 6f 6c 64 65 72 20 | if such| holder |
|00004d60| 6f 72 20 74 68 69 72 64 | 20 70 61 72 74 79 20 68 |or third| party h|
|00004d70| 61 73 20 62 65 65 6e 20 | 61 64 76 69 73 65 64 0a |as been |advised.|
|00004d80| 58 20 20 6f 66 20 74 68 | 65 20 70 6f 73 73 69 62 |X of th|e possib|
|00004d90| 69 6c 69 74 79 20 6f 66 | 20 73 75 63 68 20 64 61 |ility of| such da|
|00004da0| 6d 61 67 65 73 2e 0a 58 | 0a 58 20 20 28 34 29 20 |mages..X|.X (4) |
|00004db0| 4f 62 6a 65 63 74 20 63 | 6f 64 65 20 70 72 6f 64 |Object c|ode prod|
|00004dc0| 75 63 65 64 20 62 79 20 | 61 20 63 6f 6d 70 69 6c |uced by |a compil|
|00004dd0| 65 72 20 66 72 6f 6d 20 | 74 68 69 73 20 63 6f 64 |er from |this cod|
|00004de0| 65 20 6d 61 79 20 62 65 | 20 0a 58 20 20 69 6e 63 |e may be| .X inc|
|00004df0| 6f 72 70 6f 72 61 74 65 | 64 20 69 6e 74 6f 20 63 |orporate|d into c|
|00004e00| 6f 6d 6d 65 72 63 69 61 | 6c 20 70 72 6f 64 75 63 |ommercia|l produc|
|00004e10| 74 73 20 77 69 74 68 6f | 75 74 20 62 65 69 6e 67 |ts witho|ut being|
|00004e20| 20 73 75 62 6a 65 63 74 | 20 74 6f 20 0a 58 20 20 | subject| to .X |
|00004e30| 72 65 73 74 72 69 63 74 | 69 6f 6e 73 20 28 31 29 |restrict|ions (1)|
|00004e40| 28 61 29 20 6f 72 20 28 | 31 29 28 62 29 2e 0a 58 |(a) or (|1)(b)..X|
|00004e50| 0a 58 2a 2f 0a 58 0a 58 | 23 69 6e 63 6c 75 64 65 |.X*/.X.X|#include|
|00004e60| 20 3c 73 74 64 69 6f 2e | 68 3e 0a 58 23 69 6e 63 | <stdio.|h>.X#inc|
|00004e70| 6c 75 64 65 20 3c 6d 61 | 6c 6c 6f 63 2e 68 3e 0a |lude <ma|lloc.h>.|
|00004e80| 58 23 69 6e 63 6c 75 64 | 65 20 3c 6d 65 6d 6f 72 |X#includ|e <memor|
|00004e90| 79 2e 68 3e 0a 58 23 69 | 6e 63 6c 75 64 65 20 3c |y.h>.X#i|nclude <|
|00004ea0| 73 74 72 69 6e 67 2e 68 | 3e 0a 58 23 69 6e 63 6c |string.h|>.X#incl|
|00004eb0| 75 64 65 20 3c 61 73 73 | 65 72 74 2e 68 3e 0a 58 |ude <ass|ert.h>.X|
|00004ec0| 0a 58 23 69 6e 63 6c 75 | 64 65 20 22 73 6f 72 74 |.X#inclu|de "sort|
|00004ed0| 69 6e 67 2e 68 22 0a 58 | 0a 58 69 6e 74 20 73 68 |ing.h".X|.Xint sh|
|00004ee0| 65 6c 6c 5f 73 6f 72 74 | 28 62 61 73 65 2c 20 6e |ell_sort|(base, n|
|00004ef0| 65 6c 65 6d 2c 20 77 69 | 64 74 68 2c 20 63 6d 70 |elem, wi|dth, cmp|
|00004f00| 72 5f 66 75 6e 63 29 0a | 58 20 20 63 68 61 72 20 |r_func).|X char |
|00004f10| 2a 20 62 61 73 65 3b 0a | 58 20 20 69 6e 74 20 6e |* base;.|X int n|
|00004f20| 65 6c 65 6d 3b 0a 58 20 | 20 69 6e 74 20 77 69 64 |elem;.X | int wid|
|00004f30| 74 68 3b 0a 58 20 20 69 | 6e 74 20 28 2a 63 6d 70 |th;.X i|nt (*cmp|
|00004f40| 72 5f 66 75 6e 63 29 28 | 29 3b 0a 58 7b 0a 58 20 |r_func)(|);.X{.X |
|00004f50| 20 69 6e 74 20 67 61 70 | 2c 20 69 2c 20 6a 3b 0a | int gap|, i, j;.|
|00004f60| 58 20 20 63 68 61 72 20 | 2a 20 74 65 6d 70 3b 0a |X char |* temp;.|
|00004f70| 58 0a 58 20 20 74 65 6d | 70 20 3d 20 6d 61 6c 6c |X.X tem|p = mall|
|00004f80| 6f 63 28 77 69 64 74 68 | 29 3b 0a 58 20 20 61 73 |oc(width|);.X as|
|00004f90| 73 65 72 74 28 74 65 6d | 70 20 21 3d 20 4e 55 4c |sert(tem|p != NUL|
|00004fa0| 4c 29 3b 0a 58 0a 58 20 | 20 66 6f 72 20 28 67 61 |L);.X.X | for (ga|
|00004fb0| 70 20 3d 20 6e 65 6c 65 | 6d 20 2f 20 32 3b 20 67 |p = nele|m / 2; g|
|00004fc0| 61 70 20 3e 20 30 3b 20 | 67 61 70 20 2f 3d 20 32 |ap > 0; |gap /= 2|
|00004fd0| 29 0a 58 20 20 7b 0a 58 | 20 20 20 20 66 6f 72 20 |).X {.X| for |
|00004fe0| 28 69 20 3d 20 67 61 70 | 3b 20 69 20 3c 20 6e 65 |(i = gap|; i < ne|
|00004ff0| 6c 65 6d 3b 20 69 2b 2b | 29 0a 58 20 20 20 20 7b |lem; i++|).X {|
|00005000| 0a 58 20 20 20 20 20 20 | 66 6f 72 20 28 6a 20 3d |.X |for (j =|
|00005010| 20 69 2d 67 61 70 3b 20 | 0a 58 20 20 20 20 20 20 | i-gap; |.X |
|00005020| 20 20 20 20 20 6a 20 3e | 3d 30 20 26 26 20 28 2a | j >|=0 && (*|
|00005030| 63 6d 70 72 5f 66 75 6e | 63 29 28 62 61 73 65 2b |cmpr_fun|c)(base+|
|00005040| 6a 2a 77 69 64 74 68 2c | 20 62 61 73 65 2b 28 6a |j*width,| base+(j|
|00005050| 2b 67 61 70 29 2a 77 69 | 64 74 68 29 20 3e 20 30 |+gap)*wi|dth) > 0|
|00005060| 3b 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 6a 20 |;.X | j |
|00005070| 2d 3d 20 67 61 70 29 0a | 58 20 20 20 20 20 20 7b |-= gap).|X {|
|00005080| 0a 58 20 20 20 20 20 20 | 20 20 6d 65 6d 63 70 79 |.X | memcpy|
|00005090| 28 74 65 6d 70 2c 20 62 | 61 73 65 2b 6a 2a 77 69 |(temp, b|ase+j*wi|
|000050a0| 64 74 68 2c 20 77 69 64 | 74 68 29 3b 0a 58 20 20 |dth, wid|th);.X |
|000050b0| 20 20 20 20 20 20 6d 65 | 6d 63 70 79 28 62 61 73 | me|mcpy(bas|
|000050c0| 65 2b 6a 2a 77 69 64 74 | 68 2c 20 62 61 73 65 2b |e+j*widt|h, base+|
|000050d0| 28 6a 2b 67 61 70 29 2a | 77 69 64 74 68 2c 20 77 |(j+gap)*|width, w|
|000050e0| 69 64 74 68 29 3b 0a 58 | 20 20 20 20 20 20 20 20 |idth);.X| |
|000050f0| 6d 65 6d 63 70 79 28 62 | 61 73 65 2b 28 6a 2b 67 |memcpy(b|ase+(j+g|
|00005100| 61 70 29 2a 77 69 64 74 | 68 2c 20 74 65 6d 70 2c |ap)*widt|h, temp,|
|00005110| 20 77 69 64 74 68 29 3b | 0a 58 20 20 20 20 20 20 | width);|.X |
|00005120| 7d 0a 58 20 20 20 20 7d | 0a 58 20 20 7d 0a 58 0a |}.X }|.X }.X.|
|00005130| 58 20 20 69 66 20 28 74 | 65 6d 70 20 21 3d 20 4e |X if (t|emp != N|
|00005140| 55 4c 4c 29 20 66 72 65 | 65 28 74 65 6d 70 29 3b |ULL) fre|e(temp);|
|00005150| 0a 58 0a 58 20 20 72 65 | 74 75 72 6e 20 30 3b 0a |.X.X re|turn 0;.|
|00005160| 58 0a 58 7d 0a 45 4e 44 | 5f 4f 46 5f 46 49 4c 45 |X.X}.END|_OF_FILE|
|00005170| 0a 20 20 69 66 20 74 65 | 73 74 20 32 36 36 38 20 |. if te|st 2668 |
|00005180| 2d 6e 65 20 60 77 63 20 | 2d 63 20 3c 27 73 68 65 |-ne `wc |-c <'she|
|00005190| 6c 6c 5f 73 6f 72 74 2e | 63 27 60 3b 20 74 68 65 |ll_sort.|c'`; the|
|000051a0| 6e 0a 20 20 20 20 65 63 | 68 6f 20 73 68 61 72 3a |n. ec|ho shar:|
|000051b0| 20 5c 22 27 73 68 65 6c | 6c 5f 73 6f 72 74 2e 63 | \"'shel|l_sort.c|
|000051c0| 27 5c 22 20 75 6e 70 61 | 63 6b 65 64 20 77 69 74 |'\" unpa|cked wit|
|000051d0| 68 20 77 72 6f 6e 67 20 | 73 69 7a 65 21 0a 20 20 |h wrong |size!. |
|000051e0| 66 69 0a 20 20 23 20 65 | 6e 64 20 6f 66 20 27 73 |fi. # e|nd of 's|
|000051f0| 68 65 6c 6c 5f 73 6f 72 | 74 2e 63 27 0a 66 69 0a |hell_sor|t.c'.fi.|
|00005200| 69 66 20 74 65 73 74 20 | 2d 66 20 27 73 6f 72 74 |if test |-f 'sort|
|00005210| 69 6e 67 2e 68 27 20 2d | 61 20 22 24 7b 31 7d 22 |ing.h' -|a "${1}"|
|00005220| 20 21 3d 20 22 2d 63 22 | 20 3b 20 74 68 65 6e 20 | != "-c"| ; then |
|00005230| 0a 20 20 65 63 68 6f 20 | 73 68 61 72 3a 20 57 69 |. echo |shar: Wi|
|00005240| 6c 6c 20 6e 6f 74 20 63 | 6c 6f 62 62 65 72 20 65 |ll not c|lobber e|
|00005250| 78 69 73 74 69 6e 67 20 | 66 69 6c 65 20 5c 22 27 |xisting |file \"'|
|00005260| 73 6f 72 74 69 6e 67 2e | 68 27 5c 22 0a 65 6c 73 |sorting.|h'\".els|
|00005270| 65 0a 20 20 65 63 68 6f | 20 73 68 61 72 3a 20 45 |e. echo| shar: E|
|00005280| 78 74 72 61 63 74 69 6e | 67 20 5c 22 27 73 6f 72 |xtractin|g \"'sor|
|00005290| 74 69 6e 67 2e 68 27 5c | 22 20 5c 28 37 39 37 20 |ting.h'\|" \(797 |
|000052a0| 63 68 61 72 61 63 74 65 | 72 73 5c 29 0a 20 20 73 |characte|rs\). s|
|000052b0| 65 64 20 22 73 2f 5e 58 | 2f 2f 22 20 3e 27 73 6f |ed "s/^X|//" >'so|
|000052c0| 72 74 69 6e 67 2e 68 27 | 20 3c 3c 27 45 4e 44 5f |rting.h'| <<'END_|
|000052d0| 4f 46 5f 46 49 4c 45 27 | 0a 58 0a 58 2f 2a 20 75 |OF_FILE'|.X.X/* u|
|000052e0| 73 65 20 74 68 65 20 6e | 65 78 74 20 6c 69 6e 65 |se the n|ext line|
|000052f0| 20 69 66 20 79 6f 75 72 | 20 43 20 6c 69 62 72 61 | if your| C libra|
|00005300| 72 79 20 64 6f 65 73 20 | 6e 6f 74 20 68 61 76 65 |ry does |not have|
|00005310| 20 6d 65 6d 6d 6f 76 65 | 20 2a 2f 0a 58 0a 58 23 | memmove| */.X.X#|
|00005320| 64 65 66 69 6e 65 20 6d | 65 6d 6d 6f 76 65 28 61 |define m|emmove(a|
|00005330| 2c 20 62 2c 20 6e 29 20 | 62 63 6f 70 79 28 62 2c |, b, n) |bcopy(b,|
|00005340| 20 61 2c 20 6e 29 0a 58 | 0a 58 2f 2a 20 75 73 65 | a, n).X|.X/* use|
|00005350| 20 74 68 65 20 6e 65 78 | 74 20 6c 69 6e 65 20 69 | the nex|t line i|
|00005360| 66 20 79 6f 75 72 20 43 | 20 6c 69 62 72 61 72 79 |f your C| library|
|00005370| 20 64 6f 65 73 20 6e 6f | 74 20 68 61 76 65 20 6d | does no|t have m|
|00005380| 65 6d 63 70 79 20 2a 2f | 0a 58 0a 58 2f 2a 20 23 |emcpy */|.X.X/* #|
|00005390| 64 65 66 69 6e 65 20 6d | 65 6d 63 70 79 28 74 6f |define m|emcpy(to|
|000053a0| 2c 20 66 72 6f 6d 2c 20 | 6e 29 20 62 63 6f 70 79 |, from, |n) bcopy|
|000053b0| 28 66 72 6f 6d 2c 20 74 | 6f 2c 20 6e 29 20 20 2a |(from, t|o, n) *|
|000053c0| 2f 0a 58 0a 58 0a 58 23 | 64 65 66 69 6e 65 20 4d |/.X.X.X#|define M|
|000053d0| 41 59 42 45 5f 54 48 52 | 45 53 48 4f 4c 44 20 38 |AYBE_THR|ESHOLD 8|
|000053e0| 0a 58 65 78 74 65 72 6e | 20 69 6e 74 20 5f 6d 61 |.Xextern| int _ma|
|000053f0| 79 62 65 5f 73 6f 72 74 | 65 64 3b 0a 58 0a 58 65 |ybe_sort|ed;.X.Xe|
|00005400| 78 74 65 72 6e 20 76 6f | 69 64 20 65 78 69 74 28 |xtern vo|id exit(|
|00005410| 29 3b 0a 58 65 78 74 65 | 72 6e 20 69 6e 74 20 71 |);.Xexte|rn int q|
|00005420| 73 6f 72 74 28 29 3b 0a | 58 0a 58 65 78 74 65 72 |sort();.|X.Xexter|
|00005430| 6e 20 69 6e 74 20 6d 65 | 72 67 65 5f 73 6f 72 74 |n int me|rge_sort|
|00005440| 28 29 3b 0a 58 65 78 74 | 65 72 6e 20 69 6e 74 20 |();.Xext|ern int |
|00005450| 68 65 61 70 5f 73 6f 72 | 74 28 29 3b 0a 58 65 78 |heap_sor|t();.Xex|
|00005460| 74 65 72 6e 20 69 6e 74 | 20 62 75 62 62 6c 65 5f |tern int| bubble_|
|00005470| 73 6f 72 74 28 29 3b 0a | 58 65 78 74 65 72 6e 20 |sort();.|Xextern |
|00005480| 69 6e 74 20 71 75 69 63 | 6b 5f 73 6f 72 74 28 29 |int quic|k_sort()|
|00005490| 3b 0a 58 65 78 74 65 72 | 6e 20 69 6e 74 20 73 68 |;.Xexter|n int sh|
|000054a0| 65 6c 6c 5f 73 6f 72 74 | 28 29 3b 0a 58 65 78 74 |ell_sort|();.Xext|
|000054b0| 65 72 6e 20 69 6e 74 20 | 69 6e 73 65 72 74 69 6f |ern int |insertio|
|000054c0| 6e 5f 73 6f 72 74 28 29 | 3b 0a 58 65 78 74 65 72 |n_sort()|;.Xexter|
|000054d0| 6e 20 69 6e 74 20 62 6f | 67 6f 5f 73 6f 72 74 28 |n int bo|go_sort(|
|000054e0| 29 3b 0a 58 0a 58 2f 2a | 20 49 74 27 73 20 6d 6f |);.X.X/*| It's mo|
|000054f0| 72 65 20 69 6d 70 6f 72 | 74 61 6e 74 20 74 68 61 |re impor|tant tha|
|00005500| 74 20 74 68 65 73 65 20 | 72 65 70 72 65 73 65 6e |t these |represen|
|00005510| 74 20 63 6f 6d 6d 6f 6e | 20 73 69 7a 65 73 20 6f |t common| sizes o|
|00005520| 6e 20 79 6f 75 72 0a 58 | 20 20 20 6d 61 63 68 69 |n your.X| machi|
|00005530| 6e 65 20 74 68 61 6e 20 | 74 68 61 74 20 74 68 65 |ne than |that the|
|00005540| 79 20 72 65 70 72 65 73 | 65 6e 74 20 61 20 63 65 |y repres|ent a ce|
|00005550| 72 74 61 69 6e 20 6e 75 | 6d 62 65 72 20 6f 66 20 |rtain nu|mber of |
|00005560| 62 79 74 65 73 2e 20 2a | 2f 0a 58 0a 58 74 79 70 |bytes. *|/.X.Xtyp|
|00005570| 65 64 65 66 20 73 68 6f | 72 74 20 20 20 20 20 20 |edef sho|rt |
|00005580| 20 20 20 20 20 20 20 20 | 20 63 68 75 6e 6b 32 3b | | chunk2;|
|00005590| 0a 58 74 79 70 65 64 65 | 66 20 6c 6f 6e 67 20 20 |.Xtypede|f long |
|000055a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 63 68 | | ch|
|000055b0| 75 6e 6b 34 3b 0a 58 74 | 79 70 65 64 65 66 20 64 |unk4;.Xt|ypedef d|
|000055c0| 6f 75 62 6c 65 20 20 20 | 20 20 20 20 20 20 20 20 |ouble | |
|000055d0| 20 20 20 63 68 75 6e 6b | 38 3b 0a 58 0a 58 23 64 | chunk|8;.X.X#d|
|000055e0| 65 66 69 6e 65 20 46 4c | 4f 47 47 45 52 5f 56 45 |efine FL|OGGER_VE|
|000055f0| 52 53 49 4f 4e 20 30 0a | 58 23 64 65 66 69 6e 65 |RSION 0.|X#define|
|00005600| 20 46 4c 4f 47 47 45 52 | 5f 50 41 54 43 48 4c 45 | FLOGGER|_PATCHLE|
|00005610| 56 45 4c 20 30 0a 58 0a | 45 4e 44 5f 4f 46 5f 46 |VEL 0.X.|END_OF_F|
|00005620| 49 4c 45 0a 20 20 69 66 | 20 74 65 73 74 20 37 39 |ILE. if| test 79|
|00005630| 37 20 2d 6e 65 20 60 77 | 63 20 2d 63 20 3c 27 73 |7 -ne `w|c -c <'s|
|00005640| 6f 72 74 69 6e 67 2e 68 | 27 60 3b 20 74 68 65 6e |orting.h|'`; then|
|00005650| 0a 20 20 20 20 65 63 68 | 6f 20 73 68 61 72 3a 20 |. ech|o shar: |
|00005660| 5c 22 27 73 6f 72 74 69 | 6e 67 2e 68 27 5c 22 20 |\"'sorti|ng.h'\" |
|00005670| 75 6e 70 61 63 6b 65 64 | 20 77 69 74 68 20 77 72 |unpacked| with wr|
|00005680| 6f 6e 67 20 73 69 7a 65 | 21 0a 20 20 66 69 0a 20 |ong size|!. fi. |
|00005690| 20 23 20 65 6e 64 20 6f | 66 20 27 73 6f 72 74 69 | # end o|f 'sorti|
|000056a0| 6e 67 2e 68 27 0a 66 69 | 0a 65 63 68 6f 20 73 68 |ng.h'.fi|.echo sh|
|000056b0| 61 72 3a 20 45 6e 64 20 | 6f 66 20 61 72 63 68 69 |ar: End |of archi|
|000056c0| 76 65 20 32 20 5c 28 6f | 66 20 32 5c 29 2e 0a 63 |ve 2 \(o|f 2\)..c|
|000056d0| 70 20 2f 64 65 76 2f 6e | 75 6c 6c 20 61 72 6b 32 |p /dev/n|ull ark2|
|000056e0| 69 73 64 6f 6e 65 0a 4d | 49 53 53 49 4e 47 3d 22 |isdone.M|ISSING="|
|000056f0| 22 0a 66 6f 72 20 49 20 | 69 6e 20 31 20 32 20 3b |".for I |in 1 2 ;|
|00005700| 20 64 6f 0a 20 20 20 20 | 69 66 20 74 65 73 74 20 | do. |if test |
|00005710| 21 20 2d 66 20 61 72 6b | 24 7b 49 7d 69 73 64 6f |! -f ark|${I}isdo|
|00005720| 6e 65 20 3b 20 74 68 65 | 6e 0a 09 4d 49 53 53 49 |ne ; the|n..MISSI|
|00005730| 4e 47 3d 22 24 7b 4d 49 | 53 53 49 4e 47 7d 20 24 |NG="${MI|SSING} $|
|00005740| 7b 49 7d 22 0a 20 20 20 | 20 66 69 0a 64 6f 6e 65 |{I}". | fi.done|
|00005750| 0a 69 66 20 74 65 73 74 | 20 22 24 7b 4d 49 53 53 |.if test| "${MISS|
|00005760| 49 4e 47 7d 22 20 3d 20 | 22 22 20 3b 20 74 68 65 |ING}" = |"" ; the|
|00005770| 6e 0a 20 20 20 20 65 63 | 68 6f 20 59 6f 75 20 68 |n. ec|ho You h|
|00005780| 61 76 65 20 75 6e 70 61 | 63 6b 65 64 20 62 6f 74 |ave unpa|cked bot|
|00005790| 68 20 61 72 63 68 69 76 | 65 73 2e 0a 20 20 20 20 |h archiv|es.. |
|000057a0| 72 6d 20 2d 66 20 61 72 | 6b 5b 31 2d 39 5d 69 73 |rm -f ar|k[1-9]is|
|000057b0| 64 6f 6e 65 0a 65 6c 73 | 65 0a 20 20 20 20 65 63 |done.els|e. ec|
|000057c0| 68 6f 20 59 6f 75 20 73 | 74 69 6c 6c 20 6d 75 73 |ho You s|till mus|
|000057d0| 74 20 75 6e 70 61 63 6b | 20 74 68 65 20 66 6f 6c |t unpack| the fol|
|000057e0| 6c 6f 77 69 6e 67 20 61 | 72 63 68 69 76 65 73 3a |lowing a|rchives:|
|000057f0| 0a 20 20 20 20 65 63 68 | 6f 20 22 20 20 20 20 20 |. ech|o " |
|00005800| 20 20 20 22 20 24 7b 4d | 49 53 53 49 4e 47 7d 0a | " ${M|ISSING}.|
|00005810| 66 69 0a 65 78 69 74 20 | 30 0a 65 78 69 74 20 30 |fi.exit |0.exit 0|
|00005820| 20 23 20 4a 75 73 74 20 | 69 6e 20 63 61 73 65 2e | # Just |in case.|
|00005830| 2e 2e 0a | |... | |
+--------+-------------------------+-------------------------+--------+--------+
