*
*
* after splitting this file into the five source files:
*
* srt.h, main.c, srtbu
.c, srtinsr.c, srtmerg.c
*
* compile using the command:
*
* gcc -std=c99 -DRAND -DPRNT -DTYPE=(float | double) -D(BUBB | HEAP | INSR | MERG) *.c
*
*
*
*
* srt.h file
*
*
#ifndef SRT_H
#define SRT_H
#include
#define MAX_BUF 256
#define swap(qx,qy,sz) \
do { \
char buf[MAX_BUF]; \
char *q1 = qx; \
char *q2 = qy; \
for (size_t m, ms = sz; ms > 0; ms -= m, q1 += m, q2 += m) { \
XXXXXXXXXXm = ms < sizeof(buf) ? ms : sizeof(buf); \
XXXXXXXXXXmemcpy(buf, q1, m); \
XXXXXXXXXXmemcpy(q1, q2, m); \
XXXXXXXXXXmemcpy(q2, buf, m); \
} \
} while (0)
void srtbu
(void *, size_t, size_t, int (*)(const void *, const void *));
void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void srtinsr(void *, size_t, size_t, int (*)(const void *, const void *));
void srtmerg(void *, size_t, size_t, int (*)(const void *, const void *));
#endif /* SRT_H *
*
*
* main.c file
*
*
#include
#include
#include
#include "srt.h"
static int compare(const void *, const void *);
int main(int argc, char *argv[]) {
int nelem = argc == 2 ? atoi(argv[1]) : SHRT_MAX;
TYPE *a = calloc(nelem, sizeof(TYPE));
#ifdef RAND
for (int i = 0; i < nelem; ++i) {
XXXXXXXXXXa[i] = (TYPE)rand() / RAND_MAX;
}
#else
for (int i = 0; i < nelem; ++i) {
XXXXXXXXXXa[i] = i;
}
#endif
#if defined BUBB
srtbu
(a, nelem, sizeof(TYPE), compare);
#elif defined HEAP
srtheap(a, nelem, sizeof(TYPE), compare);
#elif defined INSR
srtinsr(a, nelem, sizeof(TYPE), compare);
#elif defined MERG
srtmerg(a, nelem, sizeof(TYPE), compare);
#else
qsort(a, nelem, sizeof(TYPE), compare);
#endif
#ifdef PRNT
for (int i = 0; i < nelem; ++i) {
XXXXXXXXXXprintf("%f\n", a[i]);
}
#else
for (int i = 0; i < nelem - 1; ++i) {
XXXXXXXXXXif (a[i] > a[i + 1]) {
XXXXXXXXXXprintf("fail\n");
XXXXXXXXXXgoto end;
}
}
printf("pass\n");
#endif
end:
free(a);
return 0;
}
static int compare(const void *p1, const void *p2) {
if (*(TYPE *)p1 < *(TYPE *)p2) {
XXXXXXXXXXreturn -5;
}
else if (*(TYPE *)p1 > *(TYPE *)p2) {
XXXXXXXXXXreturn +5;
}
return 0;
}
*
*
* srtbu
.c file
*
*
#include
#include
#include "srt.h"
void srtbu
(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
for (size_t i = nelem - 1; i > 0; --i) {
XXXXXXXXXXbool sorted = true;
XXXXXXXXXXfor (size_t j = 0; j < i; ++j) {
XXXXXXXXXXchar *qj = (char *)base + size * j;
XXXXXXXXXXchar *qn = qj + size;
XXXXXXXXXXif (compar(qj, qn) > 0) {
XXXXXXXXXXswap(qj, qn, size);
XXXXXXXXXXsorted = false;
}
}
XXXXXXXXXXif (sorted) {
eak;
}
}
return;
}
*
*
* srtinsr.c file
*
*
#include
#include
#include "srt.h"
void srtinsr(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
char buf[size], *qb = base;
for (size_t i = 1; i < nelem; ++i) {
XXXXXXXXXXmemcpy(buf, qb + size * i, size);
XXXXXXXXXXsize_t j = i;
XXXXXXXXXXwhile (j > 0 && compar(buf, qb + size * (j - 1)) < 0) {
XXXXXXXXXXmemcpy(qb + size * j, qb + size * (j - 1), size);
XXXXXXXXXXj;
}
XXXXXXXXXXmemcpy(qb + size * j, buf, size);
}
return;
}
*
*
* srtmerg.c file
*
*
#include
#include
#include "srt.h"
void srtmerg(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
char *qb = base, *ql, *qr, *qt;
size_t i, j, l, r;
if (nelem <= 1) {
XXXXXXXXXXreturn;
}
else if (nelem == 2) {
XXXXXXXXXXif (compar(qb, qb + size) > 0) {
XXXXXXXXXXswap(qb, qb + size, size);
}
XXXXXXXXXXreturn;
}
l = nelem / 2;
r = nelem - l;
ql = qt = malloc(size * l);
memcpy(ql, qb, size * l);
qr = qb + size * l;
srtmerg(ql, l, size, compar);
srtmerg(qr, r, size, compar);
i = 0; j = l;
while(i < l && j < nelem) {
XXXXXXXXXXif (compar(ql, qr) <= 0) {
XXXXXXXXXXmemcpy(qb, ql, size);
XXXXXXXXXXqb += size;
XXXXXXXXXXql += size;
XXXXXXXXXXi;
}
XXXXXXXXXXelse {
XXXXXXXXXXmemcpy(qb, qr, size);
XXXXXXXXXXqb += size;
XXXXXXXXXXqr += size;
XXXXXXXXXXj;
}
}