[C] sortowanie przez kopcowanie

Napisalem sortowanie przez kopcowanie, na podstawie pseudokodu z Cormena, program sie kompiluje, ale nie dziala najlepiej tj. wszystko jest ok, nie liczac tego, ze czasami pierwszy i drugi element tablicy jest odwrotnie posortowany, pozostale ok. Co tu jest nie tak? Jak pozbyc sie zmiennej globalnej? Czy sa jeszcze jakies bledy, nieoptymalne rozwiazania?

z gory dzieki za pomoc

#include <stdio.h>
#include <time.h>
#define N 10
//Sortowanie przez kopcowanie
int parent(int i){return i/2;};
int left(int i){if(i==0)return 1; else return 2*i;};
int right(int i){if(i==0)return 2; else return 2*i+1;};
void heapify(int t[], int i);
void build_heap(int t[]);
void heapsort(int t[]);
int heap_size = N; //jak pozbyc sie globalnej, a czy heap_size ma nie byc wyrazony przypadkiem za pomoca funkcji? bo w Cormenie pisalo               //heap_size[t]? jeżeli tak to jak to zrobic?
int main(){
 
 srand(time(0));
 int t[10];
 int i=0;
 for (i=0;i<N;++i)
 	t[i]=rand()%12;
 for (i=0;i<N;++i)
	printf("%d\t", t[i]);
 heapsort(t);
 printf("\n\n\n");
 for (i=0; i<N;++i)
	printf("%d\t", t[i]);

 
return 0;
}
void heapify(int t[], int i){   
 int largest;
 int l = left(i);
 int r = right(i);
 if (l<heap_size && t[l] > t[i])
	largest = l;
 else
	largest = i;

 if (r< heap_size && t[r] > t[largest])
	largest = r;
 if (largest != i){
 	int x;
	x=t[i];
	t[i]=t[largest];
	t[largest]=x;
	heapify(t, largest);
 }	
}
////////////////////////////////////////////////////////////////////////
void build_heap(int t[]){
 heap_size=N; 
 int i;
 for (i=N/2; i>=0; --i) 
	heapify(t,i);
}
/////////////////////////////////////////////////////////////////////////
void heapsort(int t[]){
 build_heap(t);
 int i;
 for (i=N; i>=1; --i){
 	int x=t[0];
	t[0]=t[i];
	t[i]=x;
	
	heap_size=heap_size-1;
	heapify(t,0);
 }
}

teraz dziala i pozbylem sie globalnej, mam jedno pytanie jeszcze, w komentarzu na dole programu...

#include <stdio.h>
#include <time.h>
#define N 10
//Sortowanie przez kopcowanie
int parent(int i){return i/2;};
int left(int i){if(i==0)return 1; else return 2*i;};
int right(int i){if(i==0)return 2; else return 2*i+1;};
void heapify(int t[], int i, int n);
void build_heap(int t[]);
void heapsort(int t[]);

int main(){
 
 srand(time(0));
 int t[10];
 int i=0;
 for (i=0;i<N;++i)
 	t[i]=rand()%123;
 for (i=0;i<N;++i)
	printf("%d\t", t[i]);
 heapsort(t);
 printf("\n\n\n");
 for (i=0; i<N;++i)
	printf("%d\t", t[i]);

 
return 0;
}
void heapify(int t[], int i, int n){   
 int largest;
 int l = left(i);
 int r = right(i);
 if (l<n && t[l] > t[i])
	largest = l;
 else
	largest = i;

 if (r< n && t[r] > t[largest])
	largest = r;
 if (largest != i){
 	int x;
	x=t[i];
	t[i]=t[largest];
	t[largest]=x;
	heapify(t, largest, n);
 }	
}
////////////////////////////////////////////////////////////////////////
void build_heap(int t[]){ 
 int i;
 for (i=N/2; i>=0; --i) ///???
	heapify(t,i,N);
}
/////////////////////////////////////////////////////////////////////////
void heapsort(int t[]){
 build_heap(t);
 int i;
 int n=N;
 for (i=N-1; i>=1; --i){  //dlaczego jak tu bylo i=N to nie dziala sortowanie?
 	int x=t[0];
	t[0]=t[i];
	t[i]=x;
	
	--n;
	heapify(t,0,n);
 }
}

ok, glupie pytanie, zakres tablicy... :D

Dla mnie to heapify u Ciebie jest troche przekombinowane.
Po pierwsze left liczysz 2n, a right 2n+1, wiec sie pytam po co do tego odstepne funkcje, ktore zwalniaja Ci kod ? Mozesz zdefiniowac te funkcje jako inline, wtedy powinno byc dobrze jak kompilator tego nie zignoruje.
Po drugie mozesz zalatwic cala ta funkcje heapify, instrukcja if... else if... else, wtedy kod bedzie krotszy i jeszcze szybszy, a tak to spoko ;)

ok, ala inline w C, to chyba niemozliwe, moze lepiej jako makra z operacjami bitowymi?

nie wiem tez dokladnie, o co Ci chodzi z tym "zalatwieniem funkcji heapify" ? :)

Chodzi mi o to, ze do napisania tej funkcji jest potrzebne 3x if, a nie 5x if, poniewaz musisz porownac trzy wartosci tylko, pierwsza to przodek, a dwie nastepne potomki i wybrac najwieksza, wiec nie trzeba do tego jeszcze dwoch if'ow, a po porownaniu decydujesz czy zamienic, jesli rzeczywiscie przodek nie jest najwiekszy.
Z tymi funkcjami, zeby je inline pisac to byl bardziej zart, poniewaz po co Ci dwie oddzielne funkcje do wyliczenia tych wartosci. Pomysl, ze za kazdym razem musisz alokowac troche pamieci przy wywolaniu funkcji(kompilator to zrobi) oraz musisz skoczyc do tej funkcji, wiec troche malo optymalne rozwiazanie.

To takie dwie uwagi do kodu, ale mimo to wszystko i tak dziala, tylko sugeruje Ci ze mozna to szybciej ogarnac, a chyba o to chodzi w sortowaniu przez kopcowanie.

Funkcje inline w C sa jak najbardziej mozliwe ;)
http://www.greenend.org.uk/rjk/2003/03/inline.html

Dobra z tymi if'ami to nie wazne spojrzalem teraz na kod i masz tam w sumie 3x if z jednym else. Wczoraj wydawalo mi sie, ze jest ich 5. Przepraszam za zamieszanie ;p

ok, dzieki