/*	elem_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	*/


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

#define MAX_N 100


/* ---- 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], i, auswahl;
	srand(time(NULL));

	/* Feld mit Zufallszahlen initialisieren */
	printf("Anfaenglich initialisiertes Feld:\n");
	for(i=0; i<MAX_N; ++i)
		printf("%d, ", a[i]=rand()%100+1);
	printf("\b\b  \n\n");

	printf(	"Welchen Sortieralgorithmus verwenden?\n"
		" (1) Selection Sort\n"
		" (2) Insertion Sort\n"
		" (3) Bubble Sort\n"
		" (4) Shellsort\n");
	do{
		printf(" > ");
		scanf("%d", &auswahl);
	}while(auswahl<1 || auswahl>4);

	sort_funk[auswahl-1](a, MAX_N);

	printf("Sortiertes Feld:\n");
	for(i=0; i<MAX_N; ++i)
		printf("%d, ", a[i]);

	printf("\b\b  \n\n");
	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=1, 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]; j=i;
			while(j>=h && a[j-h]>hilf){
				a[j]=a[j-h];
				j-=h;
			}
			a[j]=hilf;
		}
}