```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 ``` ```# quick sort BEGIN { for (i=0; i<=20; i++) tester(i) tester(1000) } function tester(i) { genid(x,i); sort(x,i); check(x,i); clear(x) gensort(x,i); sort(x,i); check(x,i); clear(x) genrev(x,i); sort(x,i); check(x,i); clear(x) genrand(x,i); sort(x,i); check(x,i); clear(x) } function genid(x,n, i) { for (i=1; i<=n; i++) x[i] = 1 } function gensort(x,n, i) { for (i=1; i<=n; i++) x[i] = i } function genrev(x,n, i) { for (i=1; i<=n; i++) x[i] = n + 1 - i } function genrand(x,n, i) { for (i=1; i<=n; i++) x[i] = int(n * rand()) } function check(x,n, i) { for (i=1; i= hi) return swap(A, lo, lo + int((hi-lo+1) * rand())) last = lo for (i=lo+1; i<=hi; i++) if (A[i] < A[lo]) swap(A, ++last, i) swap(A, lo, last) qsort(A, lo, last-1) qsort(A, last+1, hi) } function sort(A,n) { qsort(A, 1, n) } # move swaps inline and eliminate recursion function sort(A,n, lo,hi,i,j,t,s,p) { lo = 1; hi = n; p = 2 do { if (hi > lo) { j = lo + int((hi - lo + 1) * rand()) t = A[lo]; A[lo] = A[j]; A[j] = t j = lo for (i=lo+1; i<=hi; i++) if (A[i] < A[lo]) { j++; t = A[j]; A[j] = A[i]; A[i] = t } t = A[lo]; A[lo] = A[j]; A[j] = t if ((j - lo) < (hi - j)) { s[p] = lo; s[p+1] = j - 1; lo = j + 1 } else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 } p += 2 } else { p -= 2; lo = s[p]; hi = s[p+1] } } while (p > 0) } # insert sort small sub-arrays function sort(A,n, lo,hi,i,j,t,s,p) { lo = 1; hi = n; p = 2 do { if (hi - lo > 10) { j = lo + int((hi - lo + 1) * rand()) t = A[lo]; A[lo] = A[j]; A[j] = t j = lo for (i=lo+1; i<=hi; i++) if (A[i] < A[lo]) { j++; t = A[j]; A[j] = A[i]; A[i] = t } t = A[lo]; A[lo] = A[j]; A[j] = t if ((j - lo) < (hi - j)) { s[p] = lo; s[p+1] = j - 1; lo = j + 1 } else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 } p += 2 } else { p -= 2; lo = s[p]; hi = s[p+1] } } while (p > 0) for (i=2; i<=n; i++) { t = A[i] for (j=i; j>1 && A[j-1] > t; j--) A[j] = A[j-1] A[j] = t } } # approaching-pointers partition function sort(A,n, lo,hi,i,j,t,v,s,p) { lo = 1; hi = n; p = 2 do { if (hi - lo > 10) { i = lo + int((hi - lo + 1) * rand()) t = A[lo]; A[lo] = A[i]; A[i] = t j = lo + int((hi - lo + 1) * rand()) t = A[hi]; A[hi] = A[j]; A[j] = t if (A[hi] < A[lo]) { t = A[lo]; A[lo] = A[hi]; A[hi] = t } v = A[hi]; i = lo; j = hi do { do { i++ } while (A[i] < v) do { j-- } while (v < A[j]) t = A[i]; A[i] = A[j]; A[j] = t } while (i < j) t = A[i]; A[i] = A[hi]; A[hi] = t if ((i - lo) > (hi - i)) { s[p] = lo; s[p+1] = i - 1; lo = i + 1 } else { s[p] = i + 1; s[p+1] = hi; hi = i - 1 } p += 2 } else { p -= 2; lo = s[p]; hi = s[p+1] } } while (p > 0) for (i=2; i<=n; i++) { t = A[i] for (j=i; j>1 && A[j-1] > t; j--) A[j] = A[j-1] A[j] = t } } ```