Insertion Sort

Eine sehr einfache Implementierung eines Insertion Sorts in C

 
#include 
#define MAX 8

void insertion_sort(int *liste);
void output(int *liste);

int main(int argc, char* argv[])
{
	
	int a[] = {15, 9, 12, 1, 6, 13, 3, 4};

	output(a);
	insertion_sort(a);

	return 0;
}
void output(int *liste)
{
	int i=0;

	for(i=0; i= 0 && x < liste[j])
		{
			printf(" Vergleich: [%2d] < [%2d] n",x,liste[j]); 
			liste[j+1] = liste[j];
			//printf("   +> "); 
			//output(liste);
			j--;
		}
		
		liste[j+1] = x;
		printf(" Aufbau:    "); 
		output(liste);
	}

}

Shell Sort

Die Implementierung von Shell Sort

 
#include 
#define MAX 8

void shell_sort(int *liste);
void output(int *liste);

int main(int argc, char* argv[]) {
	int a[] = {15, 9, 12, 1, 6, 13, 3, 4};
	output(a);
	shell_sort(a);
	return 0;
}

void output(int *liste) {
	int i=0;
	for(i=0; i= h && liste[j-h]>t) {
				printf(" Vergleich: [%2d] > [%2d] \n",liste[j-h],t); 
				liste[j] = liste[j-h];
				j = j-h;
			}
			liste[j]=t;
		}
		printf(" Aufbau:    "); 
		output(liste);
	}

}

Heap Sort

Weiter gehts mit den C Übungen, jetzt ist der Heap Sort dran:

 
#include 
#define MAX 8

void heap_sort(int *liste);
void generate_MaxHeap(int *liste);
void versenke(int *liste, int i, int n);
void vertausche(int *liste, int i, int child);
void output(int *liste);

int main(int argc, char* argv[])
{
	
	int a[] = {15, 9, 12, 1, 6, 13, 3, 4};

	printf("+Start:     ");
	output(a);
	heap_sort(a);

	return 0;
}
void output(int *liste)
{
	int i=0;

	for(i=0; i0; i--)
	{
		vertausche(liste, i, 0);
		versenke(liste, 0, i);
	}
	printf("+Sortiert:  "); 
	output(liste);

}

void generate_MaxHeap(int *liste)
{
	// starte von Mitte rückwärts
	int i=0;
	for(i=MAX/2-1;i>=0;i--)
	{
		printf("   >> HEAP generieren Element [%d] -> [%d] n",i,liste[i]); 		
		versenke(liste, i, MAX);
	}
}

void versenke(int *liste, int i, int n)
{
	
	while(i <= (n/2)-1)
	{
		int child = ((i+1)*2)-1; // Linkes Blat

		//bestimmen ob rechtes Blatt existiert
		if (child + 1 <= n-1)
		{
			//rechtes Blatt existiert
			if(liste[child] < liste[child+1])
			{
				//wenn rechtes Blatt grösser ist, nimm das
				child++;
			}
		}

		//testen ob Element sinken muss
		if(liste[i] < liste[child])
		{
			//element versenken
			vertausche(liste, i, child);
			//wiederhole Vorgang mit der neuen Position		
			i = child;
		}
		else
		{
			break;
		}
		printf(" Versenke:  ");
		output(liste);

	}
}
void vertausche(int *liste, int i, int child)
{
	int z=liste[i];
	printf("   >> Tausche  [%d] mit  [%d] n",liste[i],liste[child]); 
	liste[i] = liste[child];
	liste[child] = z;
}