Code:
#ifndef SRT_H
#define SRT_H
#define MAX_BUF 256
void srtbubb(void *, size_t, size_t, int (*)(const void *, const void *));
void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void srtquik(void *, size_t, size_t, int (*)(const void *, const void *));
void srtshak(void *, size_t, size_t, int (*)(const void *, const void *));
#endif /* SRT_H */
/*
*
* main.c file
*
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include "srt.h"
int intcmp(const void *, const void *);
int main(int argc, char *argv[]) {
int size = argc == 2 ? atoi(argv[1]) : SHRT_MAX;
int *a = calloc(size, sizeof(int));
#ifdef RAND
for (int i = 0; i < size; ++i) {
a[i] = rand();
}
#else
for (int i = 0; i < size; ++i) {
a[i] = i;
}
#endif
#if defined BUBB
srtbubb(a, size, sizeof(int), intcmp);
#elif defined HEAP
srtheap(a, size, sizeof(int), intcmp);
#elif defined QUIK
srtquik(a, size, sizeof(int), intcmp);
#elif defined SHAK
srtshak(a, size, sizeof(int), intcmp);
#endif
#ifdef PRNT
for (int i = 0; i < size; ++i) {
printf("%i\n", a[i]);
}
#else
for (int i = 0; i < size - 1; ++i) {
if (a[i] > a[i + 1]) {
printf("Fail\n");
goto exit;
}
}
printf("Pass\n");
#endif
exit:
free(a);
return 0;
}
int intcmp(const void *p1, const void *p2) {
if (*(int *)p1 < *(int *)p2) {
return -5;
}
else if (*(int *)p1 > *(int *)p2) {
return +5;
}
return 0;
}
/*
*
* srtbubb.c file
*
*/
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "srt.h"
void srtbubb(void *base, size_t nelem, size_t size, int (*cmp)(const void *, const void *)) {
for (size_t i = nelem - 1; i > 0; --i) {
bool sorted = true;
for (size_t j = 0; j < i; ++j) {
char *qj = (char *)base + size * j;
char *qn = qj + size;
if (cmp(qj, qn) > 0) {
sorted = false;
char buf[MAX_BUF];
char *q1 = qj;
char *q2 = qn;
for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {
m = ms < sizeof(buf) ? ms : sizeof(buf);
memcpy(buf, q1, m);
memcpy(q1, q2, m);
memcpy(q2, buf, m);
}
}
}
if (sorted) {
break;
}
}
return;
}
/*
*
* srtquik.c file
*
*/
#include <stdlib.h>
#include <string.h>
#include "srt.h"
void srtquik(void *base, size_t nelem, size_t size, int (*cmp)(const void *, const void *)) {
if (nelem > 1) {
size_t i = 0;
size_t j = nelem - 1;
char *qi = (char *)base;
char *qj = qi + size * j;
char *qp = qj;
while (i < j) {
while (i < j && cmp(qi, qp) <= 0) {
++i;
qi += size;
}
while (i < j && cmp(qp, qj) <= 0) {
--j;
qj -= size;
}
if (i < j) {
char buf[MAX_BUF];
char *q1 = qi;
char *q2 = qj;
for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {
m = ms < sizeof(buf) ? ms : sizeof(buf);
memcpy(buf, q1, m);
memcpy(q1, q2, m);
memcpy(q2, buf, m);
}
++i;
qi += size;
}
}
if (qi != qp) {
char buf[MAX_BUF];
char *q1 = qi;
char *q2 = qp;
for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {
m = ms < sizeof(buf) ? ms : sizeof(buf);
memcpy(buf, q1, m);
memcpy(q1, q2, m);
memcpy(q2, buf, m);
}
}
++i;
qi += size;
srtquik(base, j, size, cmp);
srtquik(qi, nelem - i, size, cmp);
}
return;
}
/*
*
* srtshak.c file
*
*/
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "srt.h"
void srtshak(void *base, size_t nelem, size_t size, int (*cmp)(const void *, const void *)) {
for (size_t i = 0, j = nelem - 1; i < j; ++i, --j) {
bool sorted = true;
for (size_t k = i; k < j; ++k) {
char *qk = (char *)base + size * k;
char *qn = qk + size;
if (cmp(qk, qn) > 0) {
sorted = false;
char buf[MAX_BUF];
char *q1 = qk;
char *q2 = qn;
for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {
m = ms < sizeof(buf) ? ms : sizeof(buf);
memcpy(buf, q1, m);
memcpy(q1, q2, m);
memcpy(q2, buf, m);
}
}
}
if (sorted) {
break;
}
for (size_t k = j - 1; k > i; --k) {
char *qk = (char *)base + size * k;
char *qp = qk - size;
if (cmp(qk, qp) < 0) {
sorted = false;
char buf[MAX_BUF];
char *q1 = qk;
char *q2 = qp;
for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {
m = ms < sizeof(buf) ? ms : sizeof(buf);
memcpy(buf, q1, m);
memcpy(q1, q2, m);
memcpy(q2, buf, m);
}
}
}
if (sorted) {
break;
}
}
return;
}