/ MacHack 1998 / MacHack 1998.toast / Programming Contest / MacHack Contest.sit / MacHack Contest / Test Code Folder / Shared Test Code / myqsort.c

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 09 6d 79 71 73 6f 72 | 74 2e 63 00 00 00 00 00 |..myqsor|t.c.....|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 43 57 49 | 45 00 00 00 00 00 00 00 |.TEXTCWI|E.......|
|00000050| 00 00 00 00 00 12 fb 00 | 00 01 9a b1 66 30 54 b1 |........|....f0T.|
|00000060| 66 30 54 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |f0T.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 d6 35 00 00 |........|.....5..|
|00000080| 2f 2a 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |/*------|--------|
|00000090| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000000a0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000000b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000000c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 0d 0d |--------|------..|
|000000d0| 09 6d 79 71 73 6f 72 74 | 2e 63 0d 0d 09 54 68 69 |.myqsort|.c...Thi|
|000000e0| 73 20 72 65 65 6e 74 72 | 61 6e 74 20 61 6e 64 20 |s reentr|ant and |
|000000f0| 72 65 75 73 61 62 6c 65 | 20 6d 6f 64 75 6c 65 20 |reusable| module |
|00000100| 69 6d 70 6c 65 6d 65 6e | 74 73 20 61 20 66 61 73 |implemen|ts a fas|
|00000110| 74 20 71 75 69 63 6b 73 | 6f 72 74 20 61 6c 67 6f |t quicks|ort algo|
|00000120| 72 69 74 68 6d 2e 0d 09 | 0d 09 4f 72 69 67 69 6e |rithm...|..Origin|
|00000130| 61 6c 20 76 65 72 73 69 | 6f 6e 20 62 79 20 48 61 |al versi|on by Ha|
|00000140| 79 64 6e 20 48 75 6e 74 | 6c 65 79 2e 20 4d 6f 64 |ydn Hunt|ley. Mod|
|00000150| 69 66 69 65 64 20 74 6f | 20 73 75 70 70 6f 72 74 |ified to| support|
|00000160| 20 72 65 65 6e 74 72 61 | 6e 63 79 20 61 6e 64 0d | reentra|ncy and.|
|00000170| 09 65 72 72 6f 72 20 68 | 61 6e 64 6c 69 6e 67 20 |.error h|andling |
|00000180| 28 65 2e 67 2e 2c 20 75 | 73 65 72 20 63 61 6e 63 |(e.g., u|ser canc|
|00000190| 65 6c 73 29 20 62 79 20 | 4a 6f 68 6e 20 4e 6f 72 |els) by |John Nor|
|000001a0| 73 74 61 64 2e 0d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |stad..--|--------|
|000001b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001f0| 2d 2d 2a 2f 0d 0d 23 69 | 6e 63 6c 75 64 65 20 3c |--*/..#i|nclude <|
|00000200| 73 74 64 6c 69 62 2e 68 | 3e 0d 23 69 6e 63 6c 75 |stdlib.h|>.#inclu|
|00000210| 64 65 20 22 6d 79 71 73 | 6f 72 74 2e 68 22 0d 0d |de "myqs|ort.h"..|
|00000220| 74 79 70 65 64 65 66 20 | 73 74 72 75 63 74 20 54 |typedef |struct T|
|00000230| 53 6f 72 74 49 6e 66 6f | 20 7b 0d 09 6c 6f 6e 67 |SortInfo| {..long|
|00000240| 20 73 69 7a 65 3b 0d 09 | 53 6f 72 74 43 6d 70 46 | size;..|SortCmpF|
|00000250| 75 6e 63 74 69 6f 6e 20 | 63 6d 70 3b 0d 7d 20 54 |unction |cmp;.} T|
|00000260| 53 6f 72 74 49 6e 66 6f | 3b 0d 0d 0d 0d 2f 2a 2d |SortInfo|;..../*-|
|00000270| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000280| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000290| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000002a0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000002b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 0d 09 4d 65 6d |--------|---..Mem|
|000002c0| 53 77 61 70 20 0d 09 0d | 09 45 78 63 68 61 6e 67 |Swap ...|.Exchang|
|000002d0| 65 20 74 77 6f 20 61 72 | 72 61 79 20 65 6c 65 6d |e two ar|ray elem|
|000002e0| 65 6e 74 73 2e 0d 09 09 | 09 0d 09 45 6e 74 72 79 |ents....|...Entry|
|000002f0| 3a 09 70 20 3d 20 70 6f | 69 6e 74 65 72 20 74 6f |:.p = po|inter to|
|00000300| 20 66 69 72 73 74 20 65 | 6c 65 6d 65 6e 74 2e 0d | first e|lement..|
|00000310| 09 09 09 71 20 3d 20 70 | 6f 69 6e 74 65 72 20 74 |...q = p|ointer t|
|00000320| 6f 20 73 65 63 6f 6e 64 | 20 65 6c 65 6d 65 6e 74 |o second| element|
|00000330| 2e 0d 09 09 09 73 69 7a | 65 20 3d 20 73 69 7a 65 |.....siz|e = size|
|00000340| 20 6f 66 20 65 6c 65 6d | 65 6e 74 73 2e 0d 2d 2d | of elem|ents..--|
|00000350| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000360| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000370| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000380| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000390| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2a 2f 0d 0d 73 74 |--------|--*/..st|
|000003a0| 61 74 69 63 20 76 6f 69 | 64 20 4d 65 6d 53 77 61 |atic voi|d MemSwa|
|000003b0| 70 20 28 72 65 67 69 73 | 74 65 72 20 63 68 61 72 |p (regis|ter char|
|000003c0| 20 2a 70 2c 20 72 65 67 | 69 73 74 65 72 20 63 68 | *p, reg|ister ch|
|000003d0| 61 72 20 2a 71 2c 20 0d | 09 72 65 67 69 73 74 65 |ar *q, .|.registe|
|000003e0| 72 20 6c 6f 6e 67 20 73 | 69 7a 65 29 0d 7b 0d 09 |r long s|ize).{..|
|000003f0| 72 65 67 69 73 74 65 72 | 20 63 68 61 72 20 74 6d |register| char tm|
|00000400| 70 3b 0d 09 0d 09 77 68 | 69 6c 65 20 28 73 69 7a |p;....wh|ile (siz|
|00000410| 65 2d 2d 29 20 7b 0d 09 | 09 74 6d 70 20 3d 20 2a |e--) {..|.tmp = *|
|00000420| 70 3b 0d 09 09 2a 70 2b | 2b 20 3d 20 2a 71 3b 0d |p;...*p+|+ = *q;.|
|00000430| 09 09 2a 71 2b 2b 20 3d | 20 74 6d 70 3b 0d 09 7d |..*q++ =| tmp;..}|
|00000440| 0d 7d 0d 0d 0d 0d 2f 2a | 2d 2d 2d 2d 2d 2d 2d 2d |.}..../*|--------|
|00000450| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000460| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000470| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000480| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000490| 2d 2d 2d 2d 0d 09 43 68 | 6f 6f 73 65 4d 65 64 69 |----..Ch|ooseMedi|
|000004a0| 61 6e 0d 09 0d 09 53 65 | 6c 65 63 74 20 74 68 65 |an....Se|lect the|
|000004b0| 20 6d 65 64 69 61 6e 20 | 6f 66 20 74 68 72 65 65 | median |of three|
|000004c0| 20 61 72 72 61 79 20 65 | 6c 65 6d 65 6e 74 73 20 | array e|lements |
|000004d0| 61 6e 64 20 73 77 61 70 | 20 69 74 20 77 69 74 68 |and swap| it with|
|000004e0| 20 61 20 64 65 73 74 69 | 6e 61 74 69 6f 6e 0d 09 | a desti|nation..|
|000004f0| 65 6c 65 6d 65 6e 74 2e | 0d 09 0d 09 45 6e 74 72 |element.|....Entr|
|00000500| 79 3a 09 70 44 65 73 74 | 20 3d 20 70 6f 69 6e 74 |y:.pDest| = point|
|00000510| 65 72 20 74 6f 20 64 65 | 73 74 69 6e 61 74 69 6f |er to de|stinatio|
|00000520| 6e 20 65 6c 65 6d 65 6e | 74 2e 0d 09 09 09 70 41 |n elemen|t.....pA|
|00000530| 2c 20 70 42 2c 20 70 43 | 20 3d 20 70 6f 69 6e 74 |, pB, pC| = point|
|00000540| 65 72 20 74 6f 20 74 68 | 72 65 65 20 65 6c 65 6d |er to th|ree elem|
|00000550| 65 6e 74 73 2e 0d 09 09 | 09 73 6f 72 74 49 6e 66 |ents....|.sortInf|
|00000560| 6f 20 3d 20 70 6f 69 6e | 74 65 72 20 74 6f 20 73 |o = poin|ter to s|
|00000570| 6f 72 74 20 69 6e 66 6f | 2e 0d 09 09 09 0d 09 45 |ort info|.......E|
|00000580| 78 69 74 3a 09 66 75 6e | 63 74 69 6f 6e 20 72 65 |xit:.fun|ction re|
|00000590| 73 75 6c 74 20 3d 20 65 | 72 72 6f 72 20 63 6f 64 |sult = e|rror cod|
|000005a0| 65 2e 0d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |e..-----|--------|
|000005b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000005c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000005d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000005e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2a |--------|-------*|
|000005f0| 2f 0d 0d 73 74 61 74 69 | 63 20 4f 53 45 72 72 20 |/..stati|c OSErr |
|00000600| 43 68 6f 6f 73 65 4d 65 | 64 69 61 6e 20 28 76 6f |ChooseMe|dian (vo|
|00000610| 69 64 20 2a 70 44 65 73 | 74 2c 20 76 6f 69 64 20 |id *pDes|t, void |
|00000620| 2a 70 41 2c 20 76 6f 69 | 64 20 2a 70 42 2c 20 76 |*pA, voi|d *pB, v|
|00000630| 6f 69 64 20 2a 70 43 2c | 0d 09 54 53 6f 72 74 49 |oid *pC,|..TSortI|
|00000640| 6e 66 6f 20 2a 73 6f 72 | 74 49 6e 66 6f 29 0d 7b |nfo *sor|tInfo).{|
|00000650| 0d 09 72 65 67 69 73 74 | 65 72 20 76 6f 69 64 20 |..regist|er void |
|00000660| 2a 70 4d 65 64 69 61 6e | 3b 0d 09 72 65 67 69 73 |*pMedian|;..regis|
|00000670| 74 65 72 20 53 6f 72 74 | 43 6d 70 46 75 6e 63 74 |ter Sort|CmpFunct|
|00000680| 69 6f 6e 20 63 6d 70 3b | 0d 09 73 68 6f 72 74 20 |ion cmp;|..short |
|00000690| 72 65 73 75 6c 74 3b 0d | 09 4f 53 45 72 72 20 65 |result;.|.OSErr e|
|000006a0| 72 72 3b 0d 09 0d 09 63 | 6d 70 20 3d 20 73 6f 72 |rr;....c|mp = sor|
|000006b0| 74 49 6e 66 6f 2d 3e 63 | 6d 70 3b 0d 09 65 72 72 |tInfo->c|mp;..err|
|000006c0| 20 3d 20 28 2a 63 6d 70 | 29 28 70 41 2c 20 70 42 | = (*cmp|)(pA, pB|
|000006d0| 2c 20 26 72 65 73 75 6c | 74 29 3b 0d 09 69 66 20 |, &resul|t);..if |
|000006e0| 28 65 72 72 20 21 3d 20 | 6e 6f 45 72 72 29 20 72 |(err != |noErr) r|
|000006f0| 65 74 75 72 6e 20 65 72 | 72 3b 0d 09 69 66 20 28 |eturn er|r;..if (|
|00000700| 72 65 73 75 6c 74 20 3e | 20 30 29 20 7b 09 09 09 |result >| 0) {...|
|00000710| 09 09 09 2f 2a 20 70 41 | 20 3e 20 70 42 2c 20 77 |.../* pA| > pB, w|
|00000720| 68 61 74 20 69 73 20 70 | 43 3f 09 09 09 2a 2f 0d |hat is p|C?...*/.|
|00000730| 09 09 65 72 72 20 3d 20 | 28 2a 63 6d 70 29 28 70 |..err = |(*cmp)(p|
|00000740| 41 2c 20 70 43 2c 20 26 | 72 65 73 75 6c 74 29 3b |A, pC, &|result);|
|00000750| 0d 09 09 69 66 20 28 65 | 72 72 20 21 3d 20 6e 6f |...if (e|rr != no|
|00000760| 45 72 72 29 20 72 65 74 | 75 72 6e 20 65 72 72 3b |Err) ret|urn err;|
|00000770| 0d 09 09 69 66 20 28 72 | 65 73 75 6c 74 20 3e 20 |...if (r|esult > |
|00000780| 30 29 20 7b 09 09 09 09 | 09 2f 2a 20 70 41 20 3e |0) {....|./* pA >|
|00000790| 20 70 42 2c 20 70 41 20 | 3e 20 70 43 09 09 09 09 | pB, pA |> pC....|
|000007a0| 2a 2f 0d 09 09 09 65 72 | 72 20 3d 20 28 2a 63 6d |*/....er|r = (*cm|
|000007b0| 70 29 28 70 42 2c 20 70 | 43 2c 20 26 72 65 73 75 |p)(pB, p|C, &resu|
|000007c0| 6c 74 29 3b 0d 09 09 09 | 69 66 20 28 65 72 72 20 |lt);....|if (err |
|000007d0| 21 3d 20 6e 6f 45 72 72 | 29 20 72 65 74 75 72 6e |!= noErr|) return|
|000007e0| 20 65 72 72 3b 0d 09 09 | 09 69 66 20 28 72 65 73 | err;...|.if (res|
|000007f0| 75 6c 74 20 3e 20 30 29 | 0d 09 09 09 09 70 4d 65 |ult > 0)|.....pMe|
|00000800| 64 69 61 6e 20 3d 20 70 | 42 3b 09 09 09 09 2f 2a |dian = p|B;..../*|
|00000810| 20 70 41 20 3e 20 70 42 | 20 3e 20 70 43 09 09 09 | pA > pB| > pC...|
|00000820| 09 09 2a 2f 0d 09 09 09 | 65 6c 73 65 0d 09 09 09 |..*/....|else....|
|00000830| 09 70 4d 65 64 69 61 6e | 20 3d 20 70 43 3b 09 09 |.pMedian| = pC;..|
|00000840| 09 09 2f 2a 20 70 41 20 | 3e 20 70 43 20 3e 20 70 |../* pA |> pC > p|
|00000850| 42 09 09 09 09 09 2a 2f | 0d 09 09 7d 20 65 6c 73 |B.....*/|...} els|
|00000860| 65 20 7b 0d 09 09 09 70 | 4d 65 64 69 61 6e 20 3d |e {....p|Median =|
|00000870| 20 70 41 3b 09 09 09 09 | 09 2f 2a 20 70 43 20 3e | pA;....|./* pC >|
|00000880| 20 70 41 20 3e 20 70 42 | 09 09 09 09 09 2a 2f 0d | pA > pB|.....*/.|
|00000890| 09 09 7d 0d 09 7d 20 65 | 6c 73 65 20 7b 09 09 09 |..}..} e|lse {...|
|000008a0| 09 09 09 09 09 2f 2a 20 | 70 42 20 3e 20 70 41 2c |...../* |pB > pA,|
|000008b0| 20 77 68 61 74 20 69 73 | 20 70 43 3f 09 09 09 2a | what is| pC?...*|
|000008c0| 2f 0d 09 09 65 72 72 20 | 3d 20 28 2a 63 6d 70 29 |/...err |= (*cmp)|
|000008d0| 28 70 41 2c 20 70 43 2c | 20 26 72 65 73 75 6c 74 |(pA, pC,| &result|
|000008e0| 29 3b 0d 09 09 69 66 20 | 28 65 72 72 20 21 3d 20 |);...if |(err != |
|000008f0| 6e 6f 45 72 72 29 20 72 | 65 74 75 72 6e 20 65 72 |noErr) r|eturn er|
|00000900| 72 3b 0d 09 09 69 66 20 | 28 72 65 73 75 6c 74 20 |r;...if |(result |
|00000910| 3e 20 30 29 20 7b 0d 09 | 09 09 70 4d 65 64 69 61 |> 0) {..|..pMedia|
|00000920| 6e 20 3d 20 70 41 3b 09 | 09 09 09 09 2f 2a 20 70 |n = pA;.|..../* p|
|00000930| 42 20 3e 20 70 41 20 3e | 20 70 43 09 09 09 09 09 |B > pA >| pC.....|
|00000940| 2a 2f 0d 09 09 7d 20 65 | 6c 73 65 20 7b 09 09 09 |*/...} e|lse {...|
|00000950| 09 09 09 09 2f 2a 20 70 | 42 20 3e 20 70 41 2c 20 |..../* p|B > pA, |
|00000960| 70 43 20 3e 20 70 41 09 | 09 09 09 2a 2f 0d 09 09 |pC > pA.|...*/...|
|00000970| 09 65 72 72 20 3d 20 28 | 2a 63 6d 70 29 28 70 42 |.err = (|*cmp)(pB|
|00000980| 2c 20 70 43 2c 20 26 72 | 65 73 75 6c 74 29 3b 0d |, pC, &r|esult);.|
|00000990| 09 09 09 69 66 20 28 65 | 72 72 20 21 3d 20 6e 6f |...if (e|rr != no|
|000009a0| 45 72 72 29 20 72 65 74 | 75 72 6e 20 65 72 72 3b |Err) ret|urn err;|
|000009b0| 0d 09 09 09 69 66 20 28 | 72 65 73 75 6c 74 20 3e |....if (|result >|
|000009c0| 20 30 29 0d 09 09 09 09 | 70 4d 65 64 69 61 6e 20 | 0).....|pMedian |
|000009d0| 3d 20 70 43 3b 09 09 09 | 09 2f 2a 20 70 42 20 3e |= pC;...|./* pB >|
|000009e0| 20 70 43 20 3e 20 70 41 | 09 09 09 09 09 2a 2f 0d | pC > pA|.....*/.|
|000009f0| 09 09 09 65 6c 73 65 0d | 09 09 09 09 70 4d 65 64 |...else.|....pMed|
|00000a00| 69 61 6e 20 3d 20 70 42 | 3b 09 09 09 09 2f 2a 20 |ian = pB|;..../* |
|00000a10| 70 43 20 3e 20 70 42 20 | 3e 20 70 41 09 09 09 09 |pC > pB |> pA....|
|00000a20| 09 2a 2f 0d 09 09 7d 0d | 09 7d 0d 09 69 66 20 28 |.*/...}.|.}..if (|
|00000a30| 70 44 65 73 74 20 21 3d | 20 70 4d 65 64 69 61 6e |pDest !=| pMedian|
|00000a40| 29 20 4d 65 6d 53 77 61 | 70 28 70 44 65 73 74 2c |) MemSwa|p(pDest,|
|00000a50| 20 70 4d 65 64 69 61 6e | 2c 20 73 6f 72 74 49 6e | pMedian|, sortIn|
|00000a60| 66 6f 2d 3e 73 69 7a 65 | 29 3b 0d 09 72 65 74 75 |fo->size|);..retu|
|00000a70| 72 6e 20 6e 6f 45 72 72 | 3b 0d 7d 0d 0d 0d 0d 2f |rn noErr|;.}..../|
|00000a80| 2a 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |*-------|--------|
|00000a90| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000aa0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000ab0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000ac0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 0d 09 44 |--------|-----..D|
|00000ad0| 6f 46 61 73 74 51 53 6f | 72 74 0d 09 0d 09 45 6e |oFastQSo|rt....En|
|00000ae0| 74 72 79 3a 09 66 69 72 | 73 74 20 3d 20 70 6f 69 |try:.fir|st = poi|
|00000af0| 6e 74 65 72 20 74 6f 20 | 66 69 72 73 74 20 65 6c |nter to |first el|
|00000b00| 65 6d 65 6e 74 20 0d 09 | 09 09 09 6f 66 20 61 72 |ement ..|...of ar|
|00000b10| 72 61 79 20 69 6e 20 72 | 61 6e 67 65 20 74 6f 20 |ray in r|ange to |
|00000b20| 62 65 20 73 6f 72 74 65 | 64 2e 0d 09 09 09 6c 61 |be sorte|d.....la|
|00000b30| 73 74 20 3d 20 70 6f 69 | 6e 74 65 72 20 74 6f 20 |st = poi|nter to |
|00000b40| 65 6c 65 6d 65 6e 74 20 | 66 6f 6c 6c 6f 77 69 6e |element |followin|
|00000b50| 67 20 6c 61 73 74 20 65 | 6c 65 6d 65 6e 74 0d 09 |g last e|lement..|
|00000b60| 09 09 09 6f 66 20 61 72 | 72 61 79 20 69 6e 20 72 |...of ar|ray in r|
|00000b70| 61 6e 67 65 20 74 6f 20 | 62 65 20 73 6f 72 74 65 |ange to |be sorte|
|00000b80| 64 2e 20 0d 09 09 09 73 | 6f 72 74 49 6e 66 6f 20 |d. ....s|ortInfo |
|00000b90| 3d 20 70 6f 69 6e 74 65 | 72 20 74 6f 20 73 6f 72 |= pointe|r to sor|
|00000ba0| 74 20 69 6e 66 6f 2e 0d | 09 0d 09 45 78 69 74 3a |t info..|...Exit:|
|00000bb0| 09 66 75 6e 63 74 69 6f | 6e 20 72 65 73 75 6c 74 |.functio|n result|
|00000bc0| 20 3d 20 65 72 72 6f 72 | 20 63 6f 64 65 2e 0d 2d | = error| code..-|
|00000bd0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000be0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000bf0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000c00| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000c10| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2a 2f 0d 0d 73 |--------|---*/..s|
|00000c20| 74 61 74 69 63 20 4f 53 | 45 72 72 20 44 6f 46 61 |tatic OS|Err DoFa|
|00000c30| 73 74 51 53 6f 72 74 20 | 28 72 65 67 69 73 74 65 |stQSort |(registe|
|00000c40| 72 20 63 68 61 72 20 2a | 66 69 72 73 74 2c 20 63 |r char *|first, c|
|00000c50| 68 61 72 20 2a 6c 61 73 | 74 2c 20 54 53 6f 72 74 |har *las|t, TSort|
|00000c60| 49 6e 66 6f 20 2a 73 6f | 72 74 49 6e 66 6f 29 0d |Info *so|rtInfo).|
|00000c70| 7b 0d 09 72 65 67 69 73 | 74 65 72 20 53 6f 72 74 |{..regis|ter Sort|
|00000c80| 43 6d 70 46 75 6e 63 74 | 69 6f 6e 20 63 6d 70 3b |CmpFunct|ion cmp;|
|00000c90| 0d 09 72 65 67 69 73 74 | 65 72 20 63 68 61 72 20 |..regist|er char |
|00000ca0| 2a 69 2c 20 2a 6a 3b 0d | 09 72 65 67 69 73 74 65 |*i, *j;.|.registe|
|00000cb0| 72 20 6c 6f 6e 67 20 6e | 2c 20 73 69 7a 65 3b 0d |r long n|, size;.|
|00000cc0| 09 4f 53 45 72 72 20 65 | 72 72 3b 0d 09 73 68 6f |.OSErr e|rr;..sho|
|00000cd0| 72 74 20 72 65 73 75 6c | 74 3b 0d 09 20 09 0d 09 |rt resul|t;.. ...|
|00000ce0| 73 69 7a 65 20 3d 20 73 | 6f 72 74 49 6e 66 6f 2d |size = s|ortInfo-|
|00000cf0| 3e 73 69 7a 65 3b 0d 09 | 63 6d 70 20 3d 20 73 6f |>size;..|cmp = so|
|00000d00| 72 74 49 6e 66 6f 2d 3e | 63 6d 70 3b 0d 09 77 68 |rtInfo->|cmp;..wh|
|00000d10| 69 6c 65 20 28 28 6e 20 | 3d 20 28 6c 61 73 74 20 |ile ((n |= (last |
|00000d20| 2d 20 66 69 72 73 74 29 | 20 2f 20 73 69 7a 65 29 |- first)| / size)|
|00000d30| 20 3e 20 31 29 20 7b 0d | 09 09 69 66 20 28 6e 20 | > 1) {.|..if (n |
|00000d40| 3c 20 32 35 29 20 7b 0d | 09 09 09 4d 65 6d 53 77 |< 25) {.|...MemSw|
|00000d50| 61 70 28 66 69 72 73 74 | 20 2b 20 28 72 61 6e 64 |ap(first| + (rand|
|00000d60| 28 29 20 25 20 6e 29 20 | 2a 20 73 69 7a 65 2c 20 |() % n) |* size, |
|00000d70| 66 69 72 73 74 2c 20 73 | 69 7a 65 29 3b 0d 09 09 |first, s|ize);...|
|00000d80| 7d 20 65 6c 73 65 20 7b | 0d 09 09 09 65 72 72 20 |} else {|....err |
|00000d90| 3d 20 43 68 6f 6f 73 65 | 4d 65 64 69 61 6e 28 66 |= Choose|Median(f|
|00000da0| 69 72 73 74 2c 20 66 69 | 72 73 74 2c 20 66 69 72 |irst, fi|rst, fir|
|00000db0| 73 74 20 2b 20 28 6e 20 | 2f 20 32 29 20 2a 20 73 |st + (n |/ 2) * s|
|00000dc0| 69 7a 65 2c 20 0d 09 09 | 09 09 66 69 72 73 74 20 |ize, ...|..first |
|00000dd0| 2b 20 28 72 61 6e 64 28 | 29 20 25 20 6e 29 20 2a |+ (rand(|) % n) *|
|00000de0| 20 73 69 7a 65 2c 20 73 | 6f 72 74 49 6e 66 6f 29 | size, s|ortInfo)|
|00000df0| 3b 0d 09 09 09 69 66 20 | 28 65 72 72 20 21 3d 20 |;....if |(err != |
|00000e00| 6e 6f 45 72 72 29 20 72 | 65 74 75 72 6e 20 65 72 |noErr) r|eturn er|
|00000e10| 72 3b 0d 09 09 7d 0d 09 | 09 69 20 3d 20 66 69 72 |r;...}..|.i = fir|
|00000e20| 73 74 3b 0d 09 09 6a 20 | 3d 20 6c 61 73 74 3b 0d |st;...j |= last;.|
|00000e30| 09 09 77 68 69 6c 65 20 | 28 74 72 75 65 29 20 7b |..while |(true) {|
|00000e40| 0d 09 09 09 69 20 2b 3d | 20 73 69 7a 65 3b 0d 09 |....i +=| size;..|
|00000e50| 09 09 77 68 69 6c 65 20 | 28 69 20 3c 20 6c 61 73 |..while |(i < las|
|00000e60| 74 29 20 7b 0d 09 09 09 | 09 65 72 72 20 3d 20 28 |t) {....|.err = (|
|00000e70| 2a 63 6d 70 29 28 69 2c | 20 66 69 72 73 74 2c 20 |*cmp)(i,| first, |
|00000e80| 26 72 65 73 75 6c 74 29 | 3b 0d 09 09 09 09 69 66 |&result)|;.....if|
|00000e90| 20 28 65 72 72 20 21 3d | 20 6e 6f 45 72 72 29 20 | (err !=| noErr) |
|00000ea0| 72 65 74 75 72 6e 20 65 | 72 72 3b 0d 09 09 09 09 |return e|rr;.....|
|00000eb0| 69 66 20 28 72 65 73 75 | 6c 74 20 3e 3d 20 30 29 |if (resu|lt >= 0)|
|00000ec0| 20 62 72 65 61 6b 3b 0d | 09 09 09 09 69 20 2b 3d | break;.|....i +=|
|00000ed0| 20 73 69 7a 65 3b 0d 09 | 09 09 7d 0d 09 09 09 6a | size;..|..}....j|
|00000ee0| 20 2d 3d 20 73 69 7a 65 | 3b 0d 09 09 09 77 68 69 | -= size|;....whi|
|00000ef0| 6c 65 20 28 6a 20 3e 20 | 66 69 72 73 74 29 20 7b |le (j > |first) {|
|00000f00| 0d 09 09 09 09 65 72 72 | 20 3d 20 28 2a 63 6d 70 |.....err| = (*cmp|
|00000f10| 29 28 6a 2c 20 66 69 72 | 73 74 2c 20 26 72 65 73 |)(j, fir|st, &res|
|00000f20| 75 6c 74 29 3b 0d 09 09 | 09 09 69 66 20 28 65 72 |ult);...|..if (er|
|00000f30| 72 20 21 3d 20 6e 6f 45 | 72 72 29 20 72 65 74 75 |r != noE|rr) retu|
|00000f40| 72 6e 20 65 72 72 3b 0d | 09 09 09 09 69 66 20 28 |rn err;.|....if (|
|00000f50| 72 65 73 75 6c 74 20 3c | 3d 20 30 29 20 62 72 65 |result <|= 0) bre|
|00000f60| 61 6b 3b 0d 09 09 09 09 | 6a 20 2d 3d 20 73 69 7a |ak;.....|j -= siz|
|00000f70| 65 3b 0d 09 09 09 7d 0d | 09 09 09 69 66 20 28 69 |e;....}.|...if (i|
|00000f80| 20 3e 3d 20 6a 29 20 62 | 72 65 61 6b 3b 0d 09 09 | >= j) b|reak;...|
|00000f90| 09 4d 65 6d 53 77 61 70 | 28 69 2c 20 6a 2c 20 73 |.MemSwap|(i, j, s|
|00000fa0| 69 7a 65 29 3b 0d 09 09 | 7d 0d 09 09 69 66 20 28 |ize);...|}...if (|
|00000fb0| 6a 20 3d 3d 20 66 69 72 | 73 74 29 20 7b 0d 09 09 |j == fir|st) {...|
|00000fc0| 09 66 69 72 73 74 20 2b | 3d 20 73 69 7a 65 3b 0d |.first +|= size;.|
|00000fd0| 09 09 09 63 6f 6e 74 69 | 6e 75 65 3b 0d 09 09 7d |...conti|nue;...}|
|00000fe0| 0d 09 09 4d 65 6d 53 77 | 61 70 28 66 69 72 73 74 |...MemSw|ap(first|
|00000ff0| 2c 20 6a 2c 20 73 69 7a | 65 29 3b 0d 09 09 69 66 |, j, siz|e);...if|
|00001000| 20 28 6a 20 2d 20 66 69 | 72 73 74 20 3c 20 6c 61 | (j - fi|rst < la|
|00001010| 73 74 20 2d 20 28 6a 20 | 2b 20 73 69 7a 65 29 29 |st - (j |+ size))|
|00001020| 20 7b 0d 09 09 09 65 72 | 72 20 3d 20 44 6f 46 61 | {....er|r = DoFa|
|00001030| 73 74 51 53 6f 72 74 28 | 66 69 72 73 74 2c 20 6a |stQSort(|first, j|
|00001040| 2c 20 73 6f 72 74 49 6e | 66 6f 29 3b 0d 09 09 09 |, sortIn|fo);....|
|00001050| 69 66 20 28 65 72 72 20 | 21 3d 20 6e 6f 45 72 72 |if (err |!= noErr|
|00001060| 29 20 72 65 74 75 72 6e | 20 65 72 72 3b 0d 09 09 |) return| err;...|
|00001070| 09 66 69 72 73 74 20 3d | 20 6a 20 2b 20 73 69 7a |.first =| j + siz|
|00001080| 65 3b 0d 09 09 7d 20 65 | 6c 73 65 20 7b 0d 09 09 |e;...} e|lse {...|
|00001090| 09 65 72 72 20 3d 20 44 | 6f 46 61 73 74 51 53 6f |.err = D|oFastQSo|
|000010a0| 72 74 28 6a 20 2b 20 73 | 69 7a 65 2c 20 6c 61 73 |rt(j + s|ize, las|
|000010b0| 74 2c 20 73 6f 72 74 49 | 6e 66 6f 29 3b 0d 09 09 |t, sortI|nfo);...|
|000010c0| 09 69 66 20 28 65 72 72 | 20 21 3d 20 6e 6f 45 72 |.if (err| != noEr|
|000010d0| 72 29 20 72 65 74 75 72 | 6e 20 65 72 72 3b 0d 09 |r) retur|n err;..|
|000010e0| 09 09 6c 61 73 74 20 3d | 20 6a 3b 0d 09 09 7d 0d |..last =| j;...}.|
|000010f0| 09 7d 0d 09 72 65 74 75 | 72 6e 20 6e 6f 45 72 72 |.}..retu|rn noErr|
|00001100| 3b 0d 7d 0d 0d 0d 0d 2f | 2a 2d 2d 2d 2d 2d 2d 2d |;.}..../|*-------|
|00001110| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001120| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001130| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001140| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001150| 2d 2d 2d 2d 2d 0d 09 46 | 61 73 74 51 53 6f 72 74 |-----..F|astQSort|
|00001160| 0d 09 0d 09 53 6f 72 74 | 20 61 6e 20 61 72 72 61 |....Sort| an arra|
|00001170| 79 2e 0d 09 0d 09 45 6e | 74 72 79 3a 09 62 61 73 |y.....En|try:.bas|
|00001180| 65 20 3d 20 70 6f 69 6e | 74 65 72 20 74 6f 20 66 |e = poin|ter to f|
|00001190| 69 72 73 74 20 61 72 72 | 61 79 20 65 6c 65 6d 65 |irst arr|ay eleme|
|000011a0| 6e 74 2e 0d 09 09 09 6e | 20 3d 20 6e 75 6d 62 65 |nt.....n| = numbe|
|000011b0| 72 20 6f 66 20 61 72 72 | 61 79 20 65 6c 65 6d 65 |r of arr|ay eleme|
|000011c0| 6e 74 73 2e 0d 09 09 09 | 73 69 7a 65 20 3d 20 73 |nts.....|size = s|
|000011d0| 69 7a 65 20 6f 66 20 61 | 72 72 61 79 20 65 6c 65 |ize of a|rray ele|
|000011e0| 6d 65 6e 74 73 2e 0d 09 | 09 09 63 6d 70 20 3d 20 |ments...|..cmp = |
|000011f0| 70 6f 69 6e 74 65 72 20 | 74 6f 20 61 72 72 61 79 |pointer |to array|
|00001200| 20 65 6c 65 6d 65 6e 74 | 20 63 6f 6d 70 61 72 69 | element| compari|
|00001210| 73 6f 6e 20 66 75 6e 63 | 74 69 6f 6e 2e 0d 09 09 |son func|tion....|
|00001220| 09 0d 09 45 78 69 74 3a | 09 66 75 6e 63 74 69 6f |...Exit:|.functio|
|00001230| 6e 20 72 65 73 75 6c 74 | 20 3d 20 65 72 72 6f 72 |n result| = error|
|00001240| 20 63 6f 64 65 2e 20 0d | 2d 2d 2d 2d 2d 2d 2d 2d | code. .|--------|
|00001250| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001260| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001270| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001280| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001290| 2d 2d 2d 2d 2a 2f 0d 0d | 4f 53 45 72 72 20 46 61 |----*/..|OSErr Fa|
|000012a0| 73 74 51 53 6f 72 74 20 | 28 76 6f 69 64 20 2a 62 |stQSort |(void *b|
|000012b0| 61 73 65 2c 20 6c 6f 6e | 67 20 6e 2c 20 6c 6f 6e |ase, lon|g n, lon|
|000012c0| 67 20 73 69 7a 65 2c 20 | 53 6f 72 74 43 6d 70 46 |g size, |SortCmpF|
|000012d0| 75 6e 63 74 69 6f 6e 20 | 63 6d 70 29 0d 7b 0d 09 |unction |cmp).{..|
|000012e0| 54 53 6f 72 74 49 6e 66 | 6f 20 73 6f 72 74 49 6e |TSortInf|o sortIn|
|000012f0| 66 6f 3b 0d 09 0d 09 73 | 72 61 6e 64 28 54 69 63 |fo;....s|rand(Tic|
|00001300| 6b 43 6f 75 6e 74 28 29 | 29 3b 0d 09 0d 09 73 6f |kCount()|);....so|
|00001310| 72 74 49 6e 66 6f 2e 63 | 6d 70 20 3d 20 63 6d 70 |rtInfo.c|mp = cmp|
|00001320| 3b 0d 09 73 6f 72 74 49 | 6e 66 6f 2e 73 69 7a 65 |;..sortI|nfo.size|
|00001330| 20 3d 20 73 69 7a 65 3b | 0d 09 0d 09 72 65 74 75 | = size;|....retu|
|00001340| 72 6e 20 44 6f 46 61 73 | 74 51 53 6f 72 74 28 62 |rn DoFas|tQSort(b|
|00001350| 61 73 65 2c 20 28 63 68 | 61 72 2a 29 62 61 73 65 |ase, (ch|ar*)base|
|00001360| 20 2b 20 6e 20 2a 20 73 | 69 7a 65 2c 20 26 73 6f | + n * s|ize, &so|
|00001370| 72 74 49 6e 66 6f 29 3b | 0d 7d 0d 00 00 00 00 00 |rtInfo);|.}......|
|00001380| 00 00 01 00 00 00 01 54 | 00 00 00 54 00 00 00 46 |.......T|...T...F|
|00001390| 00 00 00 93 00 00 00 04 | 00 00 00 00 00 88 00 0b |........|........|
|000013a0| 00 53 00 69 00 6d 00 70 | 00 6c 00 65 00 53 00 6f |.S.i.m.p|.l.e.S.o|
|000013b0| 09 6d 79 71 73 6f 72 74 | 2e 63 20 4d 61 63 48 61 |.myqsort|.c MacHa|
|000013c0| 63 6b 20 43 6f 6e 74 65 | 73 74 31 2e 73 69 74 69 |ck Conte|st1.siti|
|000013d0| 02 6b 50 61 72 74 53 49 | 54 21 00 00 00 00 00 00 |.kPartSI|T!......|
|000013e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000013f0| 00 00 b1 b0 40 91 00 00 | 00 00 00 00 01 9a 00 3e |....@...|.......>|
|00001400| 00 51 00 75 00 69 00 63 | 00 6b 00 54 00 69 00 6d |.Q.u.i.c|.k.T.i.m|
|00001410| 00 65 00 02 00 02 00 00 | 00 00 00 00 00 96 ad 72 |.e......|.......r|
|00001420| 15 d8 ad 72 15 d8 00 00 | 00 00 00 00 00 00 00 00 |...r....|........|
|00001430| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001440| 00 00 61 64 72 70 43 6f | 6d 6f 80 00 ff f6 00 60 |..adrpCo|mo.....`|
|00001450| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001460| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001470| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001480| 00 00 00 48 00 0a 47 65 | 6e 65 76 61 00 00 00 00 |...H..Ge|neva....|
|00001490| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000014a0| 00 00 00 00 00 00 00 03 | 00 02 00 76 00 19 01 fa |........|...v....|
|000014b0| 02 91 00 76 00 19 01 fa | 02 91 b1 65 ea 04 00 00 |...v....|...e....|
|000014c0| 01 8a 00 00 01 9f 00 00 | 08 14 01 00 00 00 00 04 |........|........|
|000014d0| 00 01 00 01 00 00 01 00 | 00 00 01 54 00 00 00 54 |........|...T...T|
|000014e0| 00 00 00 46 03 74 9f cc | 41 00 00 00 00 1c 00 46 |...F.t..|A......F|
|000014f0| 00 01 4d 50 53 52 00 00 | 00 12 4d 57 42 42 00 00 |..MPSR..|..MWBB..|
|00001500| 00 1e 03 ed ff ff 00 00 | 00 00 00 00 00 00 03 f0 |........|........|
|00001510| ff ff 00 00 00 4c 00 00 | 00 00 00 00 00 00 00 00 |.....L..|........|
|00001520| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001530| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001540| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001550| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001560| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001570| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+