/*
 * a collection of sort algorithms
 */

/*
 * Copyright (c) 2005 Andreas Jaggi <andreas.jaggi@waterwave.ch>
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

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

void gnomesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void insertionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void selectionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void shellsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void mergesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void merge(void *a1, void *a2, size_t n, size_t m, size_t size, int (* compar)(const void *, const void *));
void bubblesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void quicksort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void heapsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void heapcreate(void *array, size_t count, size_t size, int (* compar)(const void *, const void *));
void siftdown(void *array, size_t count, size_t size, int (* compar)(const void *, const void *), int i);

int cmpint ( void const * a, void const * b );
int randcmp ( void const * a, void const * b );
void plst (int *array, size_t size);

int main ( int argc, char *argv[] ) {
	int ls = 30;
	int i;
	int *lst = (int*) malloc(ls*sizeof(int));

	for ( i = 0; i < ls; i++ ) {
		*(lst+i) = i;
	}

	srand(1);

	qsort((void*)lst, ls, sizeof(int), randcmp);
	plst(lst, ls);
	printf("\n\n");

	printf("GnomeSort\n");
	gnomesort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	qsort((void*)lst, ls, sizeof(int), randcmp);

	printf("InsertionSort\n");
	insertionsort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	qsort((void*)lst, ls, sizeof(int), randcmp);

	printf("SelectionSort\n");
	selectionsort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	qsort((void*)lst, ls, sizeof(int), randcmp);

	printf("ShellSort\n");
	shellsort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	qsort((void*)lst, ls, sizeof(int), randcmp);

	printf("MergeSort\n");
	mergesort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	qsort((void*)lst, ls, sizeof(int), randcmp);

	printf("BubbleSort\n");
	bubblesort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	qsort((void*)lst, ls, sizeof(int), randcmp);

	printf("QuickSort\n");
	quicksort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	qsort((void*)lst, ls, sizeof(int), randcmp);

	printf("HeapSort\n");
	heapsort((void*)lst, ls, sizeof(int), cmpint);

	plst(lst, ls);
	printf("\n\n");

	free(lst);

	exit(0);
}

void plst (int *array, size_t size) {
	int i;

	for ( i = 0; i < size; i++ ) {
		printf("%d, ", *(array+i));
	}
}

int randcmp ( void const * a, void const * b ) {
	return (int)(3.0*rand()/(RAND_MAX-1))-1;
}

int cmpint ( void const * a, void const * b ) {
	int const * const i = a;
	int const * const j = b;

	if ( *i > *j ) {
		return 1;
	} else {
		if ( *i < *j ) {
			return -1;
		} else {
			return 0;
		}
	}
}

void gnomesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int i = 1;
	void *t = (void*) malloc(size);

	while ( i < count ) {
		if ( compar(array+i*size, array+(i-1)*size) < 0 ) {
			memcpy(t, array+i*size, size);
			memcpy(array+i*size, array+(i-1)*size, size);
			memcpy(array+(i-1)*size, t, size);

			if ( i > 1 ) {
				i--;
			} else {
				i++;
			}
		} else {
			i++;
		}
	}

	free(t);
}

void insertionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int i,j;
	void *t = (void*) malloc(size);

	for ( i = 1; i < count; i++ ) {
		j = i-1;
		memcpy(t, array+i*size, size);

		while ( compar(array+j*size, t) > 0  && j > -1 ) {
			memcpy(array+(j+1)*size, array+j*size, size);
			j--;
		}

		memcpy(array+(j+1)*size, t, size);
	}

	free(t);
}

void selectionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int i,min,j;
	void *t = (void*) malloc(size);

	for ( i = 0; i < count-1; i++ ) {
		min = i;

		for ( j = i+1; j < count; j++ ) {
			if ( compar(array+j*size, array+min*size) < 0 ) {
				min = j;
			}
		}

		if ( i != min ) {
			memcpy(t, array+min*size, size);
			memcpy(array+min*size, array+i*size, size);
			memcpy(array+i*size, t, size);
		}
	}

	free(t);
}

void shellsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int k,j,i;
	void *t = (void*) malloc(size);

	for ( k = count; k > 0; k-- ) {
		for ( i = k; i < count; i++ ) {
			memcpy(t, array+i*size, size);
			j = i;

			while ( j+1 > k && compar(array+(j-k)*size, t) > 0) {
				memcpy(array+j*size, array+(j-k)*size, size);
				j = j-k;
			}

			memcpy(array+j*size, t, size);
		}
	}

	free(t);
}

void mergesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int m;

	if ( count > 1 ) {
		m = count/2;

		mergesort(array, m, size, compar);
		mergesort(array+m*size, count-m, size, compar);
		merge(array, array+m*size, m, count-m, size, compar);
	}
}

void merge(void *a1, void *a2, size_t n, size_t m, size_t size, int (* compar)(const void *, const void *)) {
	int i,c;
	int i1 = 0;
	int i2 = 0;
	void *s = (void*)malloc(size*(n+m));

	for ( i = 0; i < n+m; i++ ) {
		if ( compar(a1+size*i1, a2+size*i2) < 0 ) {
			c = 1;
		} else {
			c = 0;
		}

		if ((c && i1 == n) || (!c && i2 == m)) {
			c = !c;
		}

		if ( c ) {
			memcpy(s+size*i, a1+size*i1, size);
			i1++;
		} else {
			memcpy(s+size*i, a2+size*i2, size);
			i2++;
		}
	}

	memcpy(a1, s, size*(n+m));

	free(s);
}

void bubblesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int r,i;
	int c = 1;
	void *t = (void*) malloc(size);

	for ( r = count-1; c ; r-- ) {
		c = 0;

		for ( i = 0; i < r; i++ ) {
			if ( compar(array+i*size, array+(i+1)*size) > 0) {
				memcpy(t, array+i*size, size);
				memcpy(array+i*size, array+(i+1)*size, size);
				memcpy(array+(i+1)*size, t, size);
				c = 1;
			}
		}
	}

	free(t);
}

void quicksort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int q = 0;
	int p = count-1;
	void *t = (void*) NULL;
	void *t2 = (void*) NULL;

	if ( count > 1 ) {
		t = (void*) malloc(size);
		t2 = (void*) malloc(size);

		memcpy(t, array+(count-1)*size, size);

		while ( p > q ) {
			for ( ; p > 0 && compar(array+p*size, t) > -1; p-- );
			for ( ; q < count-1 && compar(array+q*size, t) < 1; q++ );

			if ( p > q ) {
				memcpy(t2, array+p*size, size);
				memcpy(array+p*size, array+q*size, size);
				memcpy(array+q*size, t2, size);
			}
		}

		memcpy(t2, array+q*size, size);
		memcpy(array+q*size, array+(count-1)*size, size);
		memcpy(array+(count-1)*size, t2, size);

		quicksort(array, q, size, compar);
		quicksort(array+(q+1)*size, count-q-1, size, compar);

		free(t);
		free(t2);
	}
}


void heapsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int i,j,s,l;
	void *t = (void*) malloc(size);

	heapcreate(array, count, size, compar);

	for ( i = count-1; i > 0; i-- ) {
		memcpy(t, array, size);
		memcpy(array, array+(i)*size, size);
		memcpy(array+(i)*size, t, size);
		s = 1;
		j = 0;

		while ( s && j < i ) {
			s = 0;

			if ( 2*j < count ) {
				if ( 2*j+1 < count ) {
					if ( compar(array+2*j*size, array+(2*j+1)*size) > 0 ) {
						l = 2*j;
					} else {
						l = 2*j+1;
					}
				} else {
					l = 2*j;
				}
			} else {
				break;
			}

			if ( l > i-1) {
				break;
			}

			if ( compar(array+l*size, array+j*size) > 0 ) {
				memcpy(t, array+l*size, size);
				memcpy(array+l*size, array+j*size, size);
				memcpy(array+j*size, t, size);
				j = l;
				s = 1;
			}
		}
	}

	free(t);
}

void heapcreate(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) {
	int i;

	for ( i = (count-2)/2; i > -1; i-- ) {
		siftdown(array, count, size, compar, i);
	}
}

void siftdown(void *array, size_t count, size_t size, int (* compar)(const void *, const void *), int i) {
	int j;
	int s = 1;
	void *t = (void*) malloc(size);

	while ( s && 2*i+1 < count ) {
		s = 0;

		if ( compar(array+2*i*size, array+(2*i+1)*size) > 0) {
			j = 2*i;
		} else {
			j = 2*i+1;
		}

		if ( compar(array+j*size, array+i*size) > 0 ) {
			memcpy(t, array+j*size, size);
			memcpy(array+j*size, array+i*size, size);
			memcpy(array+i*size, t, size);
			i = j;
			s = 1;
		}
	}

	free(t);
}