Triedenie haldou

Program Spustiteľná verzia

#include <stdio.h>
#include <conio.h>

#define N  9  /* počet prvkov vstupnej postupnosti */

/* inicializácia poľa – prvok s indexom 0 neberieme do úvahy – pre zjednodušenie */

int A[] = {0, 44, 55, 12, 42, 94, 18, 6, 67, 23};
-------------------------------------------------------------------------------------
void vymena(int i, int j)
{
	int pom = a[i];
	a[i] = a[j];
	a[j] =pom;
}
-------------------------------------------------------------------------------------
void vypis()
{
	for (int i = 1; i <= N; i++) printf("%2d ", a[i]);
	printf("\n");
}
-------------------------------------------------------------------------------------

/* spustí prvok s indexom i na správne miesto v úseku s indexami i až t */

void spusti(int i, int t) {
	int j, k;

	j = 2 * i; k = 2 * i + 1;

	if (j <= t) {
		if (a[i] >= a[j]) j = i;
		if (k <= t)
			if (a[k] > a[j]) j = k;

		if (i != j) {
			vymena(i, j);
			spusti(j, t);
		}
	}
}
-------------------------------------------------------------------------------------
void main() /* hlavný program */
{
	int i, m;

	clrscr();
	printf("Vstupna postupnost: "); vypis();

	/* vytvorenie haldy */
	for (i = (N/2); i >= 1; i--) spusti(i, N);

	printf("\nHalda: "); vypis();

	/* triedenie */
	for (m = N; m >= 2; m--) {
	vymena(1, m);              /* výmena A[1] a A[m] */
	spusti(1, m - 1);          /* obnovenie haldy */
	}

	printf("\nUtriedena postupnost: "); vypis();
}