/*	mess_sort.c -- Sourcecode unter GPL, (c) 2003 by RTC <rtc@linux-related.de>	*/
/*	Programm implementiert die elementaren Sortierverfahren: 			*/
/*	selection sort, insertion sort, bubble sort und shellsort			*/
/*	zum Selbststudium geeignet aufgrund der Beschreibungen zu den Funktionen	*/
/*	Programm misst in dieser Version die Zeit der Algos für N Elemente		*/


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

#define MAX_N 30000


/* ---- Funktionsdeklarationen --------------------------------------------------------	*/
void selection(int *a, int n);
void insertion(int *a, int n);
void bubble(int *a, int n);
void shell(int *a, int n);
void (*(sort_funk[4]))(int *a, int n)={selection, insertion, bubble, shell};

/* ---- main() ------------------------------------------------------------------------ */
int main(void){
        int a[MAX_N], temp[MAX_N], i, j;
	char *algo[]={"selection sort", "insertion sort", "bubblesort", "shellsort"};
        clock_t start, ende;
        srand(time(NULL));

        /* Feld mit Zufallszahlen initialisieren */
        for(i=0; i<MAX_N; ++i)
                a[i]=rand()%1000;
	
	printf(	"Sortiere %d Elemente...\n"
		"==========================\n", MAX_N);

        for(i=0; i<4; ++i){
		for(j=0; j<MAX_N; ++j)
                	temp[j]=a[j];
		printf("Berechne...\t"); fflush(NULL);
                start=clock();
		sort_funk[i](temp, MAX_N);
                ende=clock();
                printf("Benoetigte Zeit \"%*s\": %6.2fs\n", strlen(algo[0]), algo[i], (ende-start)/(double)CLOCKS_PER_SEC);
	}

	return 0;
}


/* ---- selection sort ----------------------------------------------------------------	*/
/* - dieser Algorithmus sortiert ein Feld, indem er es in einer äußeren Schleife von  -	*/
/* - vorn nach hintern durchläuft und in einer inneren Schleife das jeweilige Minimum -	*/
/* - des aktuellen Pfades ermittelt; am Ende der inneren Schleife wird ausgetauscht   -	*/
/* - Algorithmus benötigt ungefähr N^2/2 Vergleiche und N Austauschoperationen 	      -	*/
/* - linear für große Datensätze mit kleinen Schlüsseln				      -	*/
/* ------------------------------------------------------------------------------------	*/
void selection(int *a, int n){
	int min, i, j, hilf;
	for(i=0; i<n-1; ++i){
		min=i;
		for(j=i+1; j<n; ++j)
			if(a[j]<a[min])
				min=j;
		hilf=a[i]; a[i]=a[min]; a[min]=hilf;
	}
}

/* ---- insertion sort ----------------------------------------------------------------	*/
/* - das Feld wird hierbei sortiert, indem in einer äußeren Schleife jedes Element    -	*/
/* - der Reihe nach betrachtet wird und dann in der inneren Schleife das momentane    -	*/
/* - Element solange mit seinen Vorgängern verglichen wird, bis es nicht mehr kleiner - */
/* - einem seiner Vorgänger ist; durch das Betrachten von Anfang an wird sortiert     -	*/
/* - Algorithmus benötigt im Durchschnitt N^2/4 Vergleiche und N^2/8 Austausche	      -	*/
/* - im ungünstigsten Fall doppelte Operationen, für fast sortierte Felder linear     -	*/
/* ------------------------------------------------------------------------------------	*/
void insertion(int *a, int n){
	int hilf, i, j;
	for(i=1; i<n; ++i){
		hilf=a[i];
		for(j=i-1; j>=0 && hilf<a[j]; --j)
			a[j+1]=a[j];
		a[j+1]=hilf;
	}
}

/* ---- bubble sort -------------------------------------------------------------------	*/
/* - in einer äußeren Schleife wird das Feld von hinten nach vorn durchlaufen, in der -	*/
/* - inneren Schleife werden die Elemente des Restfeldes von vorn nach hinten der     - */
/* - Reihe nach betrachtet und mit dem Nachfolger vertauscht, wenn sie größer sind    -	*/
/* - Algorithmus benötigt im Durchschnitt N^2/2 Vergleiche und N^2/2 Austausche	      -	*/
/* - im ungünstigsten Fall werden ebensoviele Operationen benötigt...		      -	*/
/* ------------------------------------------------------------------------------------	*/
void bubble(int *a, int n){
	int hilf, i, j;
	for(i=n-1; i>0; --i)
		for(j=0; j<i; ++j)
			if(a[j]>a[j+1]){
				hilf=a[j]; a[j]=a[j+1]; a[j+1]=hilf;
			}
}

/* ---- shellsort ---------------------------------------------------------------------	*/
/* - mittels h-Sortieren wird eine Art "Vorsortierung" des Feldes erreicht, sodass    -	*/
/* - der letzte Durchgang mit h=1, welcher dem reinen insertion sort gleichkommt      -	*/
/* - sehr zügig vorankommt; bevorzugter Algorithmus für kleinere Datensätze!	      -	*/
/* - für u.a. h-Folge führt shellsort nie mehr als N^(3/2) Vergleiche aus	      -	*/
/* ------------------------------------------------------------------------------------	*/
void shell(int *a, int n){
	int h, hilf, i, j;
	for(h=1; h<=n/9; h=h*3+1);

	for(; h>0; h/=3){
		for(i=h; i<n; ++i){
			hilf=a[i];
			for(j=i-h; j>h && hilf<a[j]; j-=h);
				a[j+h]=a[j];
			a[j+h]=hilf;
		}
	}
}