/* 03May24: Eine Beispiel-Implementierung von qsort(3), aber nur mit
 * einem anderem Algorithmus: https://arxiv.org/abs/2110.01111 */

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/* Diese Funktion benutzt die gleiche Schnittstelle von qsort(3), aber
 * mit einer weniger effizienten Implementierung: */
static void mysort(void *base, size_t nmemb, size_t size,
	   int (*compar)(const void*, const void*))
{
     char *arr = (char*) base;

     for (unsigned int i = 0; i < nmemb; i++) {
	  for (unsigned int j = 0; j < nmemb; j++) {
	       /* Weil void* keine Pointer-Arithmetik unterstuetzen,
		* muessen wir den Zeiger erstmal in einen Zeiger auf
		* einen konkreten Datentypen umcasten.  Wir nehmen
		* char*, weil sizeof(char) = 1 und damit von den
		* Einheiten mit `size' zusammenpasst.  */
	       char *a, *b;
	       a = arr + size * i;
	       b = arr + size * j;
	       
	       if (compar(a, b) < 0) {
		    /* Wir muessen in diesem Fall die Speicherstellen
		     * hinter den Zeigern tauschen, und nicht die
		     * Zeiger selbst! */
		    char tmp[size];
		    memcpy(tmp, a, size); /* memcpy(x, y, n) kopiert n * byte von y zu x */
		    memcpy(a, b, size);
		    memcpy(b, tmp, size);
	       }
	  }
     }
}

/* Wir brauchen noch eine Ordnung, aber fuer qsort/mysort brauchen wir
 * eine Funktion welche den Inhalt zwischen zwei Zeigern interpretiert
 * und bestimmt ob *i > *j. */
static int more_than(const void *i, const void *j) {
     int *n, *m;
     n = (int*) i;
     m = (int*) j;
     return *m - *n;
}

/* Bonusaufgabe: Wieso funktioniert LENGTH(arr) aber nicht
 * LENGTH(ptr), wenn man ein Zeiger auf ein Array hat? */
#define LENGTH(arr) (sizeof(arr) / sizeof(*arr))

int main()
{
     static int nums[] = {
	  38, 85, 40, 93, 66, 88, 61, 80, 76, 16, 72, 26, 1,
	  22, 96, 83, 77, 13, 11, 70, 24, 45, 53, 35, 78, 51,
	  92, 4, 89, 12, 32, 62, 14, 44, 28, 68, 59, 8, 7, 81,
	  100, 99, 29, 43, 20, 25, 79, 39, 15, 57, 60, 27, 2,
	  95, 56, 97, 74, 17, 19, 94, 69, 9, 86, 50, 33, 34,
	  18, 63, 49, 84, 75, 23, 5, 71, 58, 37, 41, 47, 54,
	  48, 82, 3, 55, 30, 90, 67, 46, 36, 65, 64, 21, 10,
	  52, 31, 42, 6, 91, 73, 98, 87
     };

     mysort(nums, LENGTH(nums), sizeof(*nums), more_than);

     for (unsigned i = 0; i < LENGTH(nums); i++) {
	  printf("%d\n", nums[i]);
     }

     return 0;
}