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

?Download download.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <stdio.h>
#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; i<MAX; i++)
	{
		printf("[%2d] ",liste[i]);
	}
	printf("n");
}
 
 
void heap_sort(int *liste)
{
	int i=0;
 
	generate_MaxHeap(liste);
	printf(" Heap:      "); 
	output(liste);
 
	printf("+Sortieren: "); 
 
	for(i=MAX-1; i>0; 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;
}

Tags: , ,