#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;
}