/*
 * ======= Studiumsumgebung =======
 * File : Sortierhilfe.c
 * Date : 08.02.2012
 * 
 * Author: V36374
 * ======= 2012 =======
 */

/*
 *	Kurze Beschreibung:
 *
 *	Dieses Programm dient lediglich nur dazu, die erlernten Sortieralgorithmen besser verstehen zu koennen. Es gibt keine Hinweise fuer die Handhabung
 *	mit den Sortieralgorithmen. Erstellt wurde dieses Programm nur zur Selbstkontrolle und zur Fehlerueberpruefung.
 *
 *	Alle Sortierverfahren wurde aus dem Skript Grundgebiete der Informatik 1 von Prof. Dr. Rainer Leupers entnommen und leicht abgewandelt, um eine
 *	lesbare Ausgabe zu erzeugen.
 *
 *	Ich uebernehme fuer eventuelle Schaeden, die durch dieses Programm entstehen koennten, keine Haftung und sage: Benutzung auf eigene Gefahr!
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void exchange(int *a, int *b);
int partition(int A[], int l, int r);
void quick_sort(int A[], int l, int r);
void selection_sort(int A[], int l, int r);
void insertion_sort(int A[], int l, int r);
void bubble_sort(int A[], int l, int r);
void sink(int N, int k, int A[]);
void heap_sort(int A[], int N);

int main(void) {
start:
	printf("Willkommen! Dieses Programm hilft dabei verschiedene Sortieralgorithmen besser zu verstehen. "
		   "Es funktioniert am besten mit Zahlen, daher benutze ich "
           "hier nur zu sortierende Zahlenarrays! \n"
           "Wie gross ist das zu sortierende Zahlenarray?\n");
	int size;
	scanf("%d",&size);
	int array[size],arrayorigin[size],arrayh[size+1];
	arrayh[0] = 0;
	printf("Das Array ist %d Elemente gross. Bitte gebe diese Elemente jetzt willkuerlch ein um die verschiedenen Algorithmen kennenzulernen: \n",size);
	int i=0,tmp;
	while(i<size) {
		scanf("%d",&tmp);
		arrayorigin[i] = tmp;
		arrayh[i+1] = tmp;
		i++;
	}


sortieren:
	for(i=0;i<size;i++)
		array[i] = arrayorigin[i];
	printf("Welchen Sortieralgorithmus sollen wir benutzen? Du hast folgende Auswahl: \n"
           "1 : SelectionSort\n"
           "2 : InsertionSort\n"
           "3 : BubbleSort\n"
           "4 : QuickSort\n"
           "5 : HeapSort\n"
           "\n");
	scanf("%d",&tmp);

	switch(tmp) {
		case 1:
			selection_sort(array,0,size-1);
			break;
		case 2:
			insertion_sort(array,0,size-1);
			break;
		case 3:
			bubble_sort(array,0,size-1);
			break;
		case 4:
			quick_sort(array,0,size-1);
			break;
		case 5:
			printf("A(B,C) -> B und C sind Kinder von A; A(B) -> B ist Kind von A; A() -> A ist Kinderlos (gluecklich)\n");
			heap_sort(arrayh,size);
			for(i=0;i<size;i++)
				array[i] = arrayh[i+1];
			break;
	}

	for(i=0;i<size;i++)
		printf(" %d ",array[i]);
	printf("\n\nVon Vorne?\n2 = gleiches Array, anderer Algorithmus\n1 = Ja\n0 = nein\n");
	scanf("%d",&tmp);
	if(tmp == 1)
		goto start;
	else if(tmp == 2)
		goto sortieren;
	else
		return 1;
}

void exchange(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int A[], int l, int r) {
    int i,j,k,v;
    k = r;
    v = A[k];
    i = l;
    j = r-1;
    while(1) {
        while(A[i] <= v && i < r)
            i++;
        while(A[j] >= v && j >= l)
            j--;
        if(i >= j)
            break;
        else {
            //printf("%d<=>%d\n",A[i],A[j]);
            exchange(&A[i],&A[j]);
        }
    }
    //printf("%d<=>%d\t",A[i],A[k]);
    exchange(&A[i],&A[k]);
    printf("Return: %d\tentspricht Arraywert: %d\n",i,A[i]);
    return i;
}

void quick_sort(int A[], int l, int r) {
	int k;
	if(r<=l)
		return;

    printf("\n");
    for(k=l;k<=r;k++)
        printf(" %d ",A[k]);
    printf("\n");

	k = partition(A,l,r);
	quick_sort(A,l,k-1);	// linken teil von k sortieren
	quick_sort(A,k+1,r);	// rechten teil von k sortieren
}

void selection_sort(int A[], int l, int r) {
	int i,j,min,k;
	for(i=l ; i<r ; i++) {				// N - 1 Iterationen
		min = i;
		for(j=i+1;j<=r;j++)			// N - 2 Iterationen
			if(A[j]<A[min])
				min = j;			// O(1) Operationen
		exchange(&A[i],&A[min]);	// O(1) Operationen
		for(k=l;k<=r;k++)
			printf(" %d ",A[k]);
		printf("\n");
	}
}

void insertion_sort(int A[], int l, int r) {
	int i,j,v,k;
	for(i=l+1 ; i<=r ; i++) {		// N - 1 Iterationen
		v = A[i];					// O(1)
		for(j=i-1;j>=l;j--) 		// N - 2 Iterationen
			if(v < A[j])
				A[j+1] = A[j];		// O(1)
			else
				break;
		A[j+1] = v;					// O(1)
		for(k=l;k<=r;k++)
			printf(" %d ",A[k]);
		printf("\n");
	}
}

void bubble_sort(int A[], int l, int r) {
	int i,j,k,durchlauf=0;
	for(i=l;i<r;i++)						// N-1 Iterationen
		for(j=r;j>i;j--) {					// N-i Iterationen -> N-1 Iterationen
			if(A[j-1] > A[j])
				exchange(&A[j-1],&A[j]);	// O(1)
			printf("%d: \t",durchlauf++);
			for(k=l;k<=r;k++)
				printf("%d \t",A[k]);
			printf("\n");
		}
}

void heap_sort(int A[], int N) { // ohne A[0]
	int i=0,j=0;

	for(i=(int)N/2;i>0;i--)
		sink(N,i,A);			// erstmal den Heap erstellen!

	for(i=1;i<=N;i++)
		if(2*i+1 <= N)
			printf("%d(%d %d) ",A[i],A[2*i],A[2*i+1]);
		else if(2*i <= N)
			printf("%d(%d) ",A[i],A[2*i]);
		else
			printf("%d() ",A[i]);
	printf("\n\n\tDer Heap ist aufgebaut, jetzt wird sortiert!\n\n"
			"Bei der folgenden Ausgabe sollte nicht allzusehr auf den Heap geachtet werden. Hier werden lediglich nur nurtzliche Infos bereitgestellt,"
			"ohne den Heap zu 100%% anzeigen zu koennen.\n\n");

	for(i=N;i>=1;i--) {
        // Ausgabe!
        for(j=1;j<=i;j++)
            if(2*j+1 <= N)
                printf("%d(%d %d) ",A[j],A[2*j],A[2*j+1]);
            else if(2*j <= N)
                printf("%d(%d) ",A[j],A[2*j]);
            else
                printf("%d() ",A[j]);
        printf("\nEntnehme:\t%d\n",A[1]);

		exchange(&A[1],&A[i]);	// Minimum an die Wurzel setzen
		sink(i-1,1,A);			// Heap wieder reparieren
	}
}

void sink(int N, int k, int A[]) {
    int son;
    while(1) {
        if(2*k > N) break;
        if(2*k+1 <= N)
            if(A[2*k] < A[2*k+1]) son = 2*k;
            else son = 2*k+1;
        else son = 2*k;
        if(A[k] > A[son]) { // Wenn der Vater groesser als der Sohn ist => wechseln!
            exchange(&A[k],&A[son]);
            k = son;
        } else break;
    }
}