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;
}

Schreibe einen Kommentar

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.