/* a-wada/qsortlib/ccg/qsortad.c Sep. 7, 2002 */ /* Copyright (c) 2002 Akira Wada */ /* <<< Example of QSORTBASE to generate sort subroutine >>> */ /* A template of the tailor-made quick sort for an application */ /* *** customizing "qsortbase.h" for distribution diagram *** */ /*----------------------------------------------------------------------------*/ /** define the object to be sorted **/ typedef struct { int nmb; char *grp; double sum; int klg; char text[108];} typeA; /** specify things depend on the object & sorting spec **/ extern int dgx, cmpf, /* cmpf : uniquekey significant [1 : yes, 2 : no] */ c6, m6; /* c6, m6 : counter of comp & swap */ #define HSKPOB if (cmpf == 2) for (i = 0; i < N; i++) A[i].nmb = 0 #define KPOB(i) RV ((int) (A[i].sum * 7.7 / 8.8 + 0.1)) /* <-descending order */ /** specify the sorting parameters **/ #include #define QSNAME qsortad #define ARGSM typeA A[], int N #define KLG1 16 #define COMPM(i, j) ((c6++, cmp = strncmp ( \ A[i].grp, A[j].grp, KLG1)) != 0 ? cmp : ( \ A[i].sum > A[j].sum ? -1 : ( \ A[i].sum < A[j].sum ? 1 : \ A[i].nmb - A[j].nmb ))) /* <- uniquekey for stability */ #define SWAPM(i, j) m6 += 2, SWAPW (A, i, j, sizeof (typeA)) #define ROTATEM(i, j, k) m6 += 3, ROTATEW (A, i, j, k, sizeof (typeA)) /** distribution diagram after partitioning **/ #include #define DDV 16 #define ADWRK int cp = 0, pd = 0, pg = 0, t; char ll[80] #define ADHSKP min = N, avr = 0, max = 0; cldst (); HSKPOB #define ADPDSH if (psz > N / DDV && --pd <= 0) do { \ bcdst (A, N); printf ("\np%d * Distribution after " \ "%d partitionings * ", ++pg, cp); \ if (sms != 0) printf (" same as previos ***"); else \ ADPDST; \ if (cp == 0) printf ("\n * min = %d avr = %d " \ " max = %d *\n", min, avr, max); \ printf ("\n * dgn=%d * l,r=[%d,%d] ", dgn, l, r); \ ADPDSM ("Initial *\n ");} while (0) #define ADPDSM(x) if (COND) printf (" * pvt=[%d,%d] %s*", m, KP (m), x) #define ADPDSN(x) if (COND) do { \ if (l == k) printf (" * pvt=[%d,%d] %s*", m, KP (m), x); \ else printf (" * pvt=[%d,%d,%d] %s*", i+ESZ, j-ESZ, \ KP (m), x);} while (0) #define ADOCPP cp++ #define ADPSKP if (COND) do { \ printf (" * partitioning skipped, already sorted" \ " [%d,%d] *", l, r); ADHLT;} while (0) #define ADPDSE printf ("\np%d * Sorting Result after %d partitionings * ", \ ++pg, cp); bcdst (A, N); ADPDST #define KP(i) KPOB (i) #define qscin fgets (ll, sizeof (ll), stdin), sscanf #define COND psz > N / DDV && pd <= 0 #define RV(i) (N - 1 - (i)) #define ADHLT if (COND) do { \ printf (" * next CR =: "), qscin (ll,"%d", &pd); \ if (pd > 0) printf ("\n * printing Dist. * %d * " \ "times skipped *", pd);} while (0) #define ADPDST do { \ prdst (N, cp); printf ("\n key /"); \ for (t = 0; t < DDV; t++) printf ("...*"); \ printf ("\n pos 0"); for (t = 2; t <= DDV; t += 2) \ printf ("%8d", t * N / DDV); printf ("\n");} while (0) static int min, max, sms, avr, P[DDV][DDV], Q[DDV][DDV]; static void cldst (void) { int i, j; for (i = 0; i < DDV; i++) for (j = 0; j < DDV; j++) Q[i][j] = 0;} static void bcdst (typeA *A, int N) { int i, j; for (i = 0; i < DDV; i++) for (j = 0; j < DDV; j++) P[i][j] = 0; for (i = 0; i < N; i++) P[RV (KP (i)) * DDV / N][i * DDV / N]++; for (i = 0; i < DDV; i++) { for (j = 0; j < DDV && P[i][j] == Q[i][j]; j++); if (j < DDV) break;} if (i == DDV && j == DDV) sms = 1; else sms = 0;} static void prdst (size_t N, int cp) { int i, j, n; for (i = 0; i < DDV; i++) { printf ("\n%5d *", RV ((i + 1) * N / DDV) + 1); for (j = 0; j < DDV; j++) printf ("%4d", (Q[i][j] = P[i][j]));} if (cp == 0) { for (i = n = 0; i < DDV; i++) for (j = 0; j < DDV; j++) { if (P[i][j] != 0) { if (P[i][j] < min) min = P[i][j]; n++, avr += P[i][j]; if (P[i][j] > max) max = P[i][j];}} avr = (avr * 2 + n) / (2 * n);}} /** call the sorting algorithm (QSORTBASE) **/ #define ARGS ARGSM typedef int PTRTYP; #define DFWRK STACK; SWAPWK; ADWRK #define VALID N > 1 #define HSKP l = 0, r = N - 1; if (dgn == 0) dgn = dgx; ADHSKP #define ESZ 1 #define COMP(i, j) COMPM (i, j) #define SWAP(i, j) SWAPM (i, j) #define ROTATE(i, j, k) ROTATEM (i, j, k) #define CLNUP ADPDSE #define STACK PTRTYP s[STKSZ], *p = s #define STKSZ sizeof (int) * 8 * 2 #define PUSH(x, y) *(p++) = x, *(p++) = y #define EMPTY (s >= p) #define POP(y, x) y = *(--p), x = *(--p) #define SWAPWK char *a, *b, *c #define SWAPW(M, i, j, L) a = (char *)&M[i], b = (char *)&M[j], swap (a, b, L) #define ROTATEW(M, i, j, k, L) a = (char *)&M[i], b = (char *)&M[j], \ c = (char *)&M[k], rotate (a, b, c, L) void swap (char *, char *, size_t); void rotate (char *, char *, char *, size_t); /* #include "qsortbase.h" * <- copy below to customize */ #define QSORTBASECT(qsortname) \ void qsortname (ARGS) { /*01*/\ PTRTYP i, j, k, l, m, n, r; int psz, thr, cmp; DFWRK; DFDGN; /*02*/\ if (VALID) { /*03*/\ HSKP; for ( ; ; ) { /*04*/\ m = l + ((psz = (r - l) / ESZ) / 2) * ESZ, psz -= (MDA); /*05*/\ ADPDSH; /* customized */\ i = l, j = r, thr = MDT; AVDGN; /*06*/\ for ( ; ; ) { /*07*/\ if (COMP (m, j) <= 0) { /*08*/\ if (i < m && COMP (i, m) > 0) { RSTCS; /*09*/\ FINDXC (MIN, i, j, r, m);}} /*10*/\ else { RSTCS; /*11*/\ if (i >= m || COMP (i, m) > 0) SWAP (i, j); else /*12*/\ FINDXC (MAX, j, l, i, m);} /*13*/\ i += ESZ, j -= ESZ; /*14*/\ if (psz > thr) thr *= MDM; else break;} CKSRT; /*15*/\ if (i < j) { /*16*/\ ADPDSM ("aft MED "); ADOCPP; /* customized */\ for (k = l; ; ) { /*17*/\ while (i < m && (cmp = COMP (i, m)) <= 0) { /*18*/\ if (cmp == 0) EQKLEFT (i, k); i += ESZ;} /*19*/\ while (m < j && (cmp = COMP (m, j)) < 0) j -= ESZ; /*20*/\ if (i < j) SWAP (i, j); else break; /*21*/\ if (cmp == 0) EQKLEFT (i, k); /*22*/\ if (m == j) m = i, j -= ESZ; else /*23*/\ if (i == m) m = j, i += ESZ; else /*24*/\ j -= ESZ, i += ESZ;} /*25*/\ i -= ESZ; j += ESZ; if (l < k) EQKWTBE (i, k); CKDGN; /*26*/\ ADPDSN ("aft PART "); ADHLT; /* customized */\ if (i - l < r - j) { /*27*/\ if (l >= i) l = j; else PUSH (j, r), r = i;} /*28*/\ else { /*29*/\ if (j >= r) r = i; else PUSH (l, i), l = j;} /*30*/\ if (l < r) continue;} /*31*/\ if (!EMPTY) POP (r, l); else break;} /*32*/\ CLNUP;}} /*33*/ #define FINDXC(MIN, i, j, r, m) do { \ n = i, k = j; do \ if (COMP (k, n) MIN 0) n = k; while ((k += ESZ) <= r); \ if (n == i) SWAP (m, i); else ROTATE (m, n, i);} while (0) #define MIN < #define MAX > #define EQKLEFT(i, k) do { /* gather equal keys to left end */\ if (k < i) SWAP (k, i); k += ESZ;} while (0) #define EQKWTBE(i, k) do { /* move equal keys to where to be */\ for (n = l; n < k && k <= i; ) { \ SWAP (n, i); n += ESZ, i -= ESZ;} \ if (k > i) i = n - ESZ;} while (0) #define MDT 16 /* threshold for median of the 5 or the more, MDT >= 8 */ #define MDA 2 /* adjusting threshold slightly, MDT + MDA >= 4 */ #define MDM 2 /* multiplier for threshold, MDM >= 2 */ /* for prevention from the degeneration caused by peculiar input */ #define DGT 128 /* <-256 threshold of p-size for checking degeneration */ #define DGV 16 /* 16 degeneration assumed if the smaller < DGL */ #define DGM 0 /* 0 threshold for selecting no median */ #define DGS 1 /* <- 2 threshold for samples distributed uniformly */ #define DGU 2 /* <- 4 threshold for sampling at random */ #define DGL (psz / DGV) * ESZ #define DFDGN int dgn = 0, nsp, itv, cst #define CKDGN if (psz >= DGT && (j < l + DGL || i > r - DGL)) do { \ dgn++; printf ("\n ** DGN=%d psz=%d ptl=%d ptr=%d **", \ dgn, psz, (j - l)/ESZ, (r - i)/ESZ);} while (0) #define AVDGN cst = 1; if (psz <= MDT || dgn <= DGM || dgn > DGS) { \ if (psz > MDT && dgn > DGS) do { \ if (dgn <= DGU) { \ nsp = 3; while (psz > thr) thr *= MDM, nsp += 2; \ itv = (psz / (nsp - 1)) * ESZ, k = l, n = r; \ for (thr = MDT; psz > thr; thr *= MDM) { \ i += ESZ, k += itv; SWAP (i, k); \ j -= ESZ, n -= itv; SWAP (n, j);}} \ else { \ if (dgn == DGU + 1) dgn++, srandom (time (0)); \ for (thr /= MDM; psz > thr; thr *= MDM) { \ SMPLRDM (i, i, j); i += ESZ; \ SMPLRDM (j, i, j); j -= ESZ;} \ SMPLRDM (m, i, j);} \ i = l, j = r, thr = MDT;} while (0) #define SMPLRDM(m, i, j) if (m != (n = i + ESZ * ( \ random () % ((j - (i)) / ESZ + 1)))) SWAP (m, n) #define RSTCS cst = 0 #define CKSRT } if (psz > MDT && cst != 0) do { \ k = l, n = l + ESZ; \ while (k < r && COMP (k, n) <= 0) k += ESZ, n += ESZ; \ if (k >= r) { i = j; \ ADPSKP;} /* customized */\ else if (k >= m) i = m;} while (0) #include #include #undef random() /* if borland bcc32 */ void srandom (unsigned long); /* * if not in */ unsigned long random (void); /* * if not in */ /* "qsortbase.h" end */ QSORTBASECT (QSNAME) /* a-wada/qsortlib/ccg/qsortad.c end */