codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <stdio.h> #include <stdlib.h> #include <string.h> /*#define DEBUG*/ #if defined(DEBUG) #include "qzmalloc.h" #else #define qzmalloc(x, y) malloc(x) #define qzfree(x, y) free(x) #define qzmallocdump() #endif #define ID_TMP 1001 #define ID_PV 1002 #define ID_PIVOT 1003 #define N 10 static int buff[N]; void swap(void *a, void *b, void *t, int size) { memcpy(t, a, size); memcpy(a, b, size); memcpy(b, t, size); } void myqsort(void *buff, int n, int size, int (*f)(const void *, const void *), int mark) { int px, flag; void *pi, *qi, *t, *pivot, *pv; if (n == 0) return; if (n == 1) return; if ((t = qzmalloc(size, ID_TMP)) == 0) return; if (n == 2) { if (f(buff, buff + size) > 0) swap(buff, buff + size, t, size); qzfree(t, ID_TMP); return; } flag = 0; if ((pv = qzmalloc(size, ID_PV)) == 0) return; if ((pivot = qzmalloc(size, ID_PIVOT)) == 0) return; memcpy(pv, buff, size); for (px = 1; px < n; px++) { if (f((int *)(buff + size * px), pv) > 0) { memcpy(pivot, buff + size * px, size);/* pivot = *(int *)(buff + size * px);*/ flag = 1; break; } else if (f((int *)(buff + size * px), pv) < 0) { memcpy(pivot, pv, size); /* pivot = pv; */ flag = 1; break; } } qzfree(pv, ID_PV); if (!flag) { qzfree(t, ID_TMP); qzfree(pivot, ID_PIVOT); return; } pi = buff; qi = buff + size * (n - 1); for (;;) { char c; while (f(pi, pivot) < 0) pi += size; while (f(qi, pivot) >= 0) qi -= size; if (qi < pi) break; swap(pi, qi, t, size); } myqsort(buff, (pi - buff) / size, sizeof(int), (int (*)(const void *, const void *))f, 2); myqsort(pi, n - ((pi - buff) / size), sizeof(int), (int (*)(const void *, const void *))f, 3); qzfree(t, ID_TMP); qzfree(pivot, ID_PIVOT); } int f(int *a, int *b) { return *a - *b; } #define SEED 31415926 int main() { int i, flag, pos, n; n = N; srand(SEED); for (i = 0; i < n; i++) buff[i] = rand() % 3000; /* buff[0] = 5; buff[1] = 3; buff[2] = 3; n = 3; */ myqsort(buff, n, sizeof(int), (int (*)(const void *, const void *))f, 1); flag = 0; for (i = 0; i < n; i++) { printf("%d,", buff[i]); if (i < n -1) if (!(buff[i] <= buff[i + 1])) { flag = 1; pos = i; } } putchar('\n'); if (flag) printf("%d:%d > %d:%d, out of order.\n", pos, buff[pos], pos + 1, buff[pos + 1]); qzmallocdump(); return 0; } /* end */
Private
[
?
]
Run code
Submit