/* Fila contains sorting functions. Heap sort algorithm, complexity O(nlogn) $Id: sort.c,v 1.1 2005/07/03 23:21:34 jefbed Exp $ */ #include #define TRUE 1 #define FALSE 0 #define WIEKSZY 1 #define MNIEJSZY -1 #define ROWNY 0 #include "sort.h" /** swaps A,B I don't know if this is portable it works correct with gcc. */ #define SWAP(a, b, rozmiar) \ { \ register char *a_ptr=(char *)a; \ register char *b_ptr=(char *)b; \ register char temp; \ register int rozm = rozmiar; \ \ while(rozm-->0) \ { \ temp = *a_ptr; \ *a_ptr++ = *b_ptr; \ *b_ptr++ = temp; \ } \ \ } /** Computes left child index in heap. */ #define LEFT( i ) \ { \ i<<=1; \ } /** Computes right child index in heap. */ #define RIGHT( i ) \ { \ i=(i<<1)+1; \ } /** Restores heap for i element. Parameters: - tablica - heap which we want to, - i - index to element wich we want to be heap, - wlkEl - size of single element, - rozm - size of heap, - porownanie - comparison function. */ static void heapify(void *tablica, unsigned long i, const size_t wlkEl, unsigned int rozm, int (*porownanie)(const void *, const void *)) { int koniec; register unsigned int l; register unsigned int p; register unsigned int largest; register char *pierwszy=(char *)tablica; /* Restores heap for i element. */ do{ koniec=TRUE; p = l = i; LEFT(l); RIGHT(p); if(l<=rozm && (*porownanie)((pierwszy+l*wlkEl),(pierwszy+i*wlkEl))>0 ) largest=l; else largest=i; if(p<=rozm && (*porownanie)((pierwszy+p*wlkEl),(pierwszy+largest*wlkEl))>0 ) largest=p; if(largest!=i){ SWAP((pierwszy+i*wlkEl), (pierwszy+largest*wlkEl), wlkEl); i=largest; koniec=FALSE; } }while(koniec!=TRUE); } /* Builds heap. Parameters: - tablica - array, - wlk - number of elements in array, - wlkEl - size of element, - rozm - number of elements of heap, - porownanie - comparison function. */ static void buildHeap(void *tablica, unsigned long wlk, const size_t wlkEl, unsigned long *rozm, int (*porownanie)(const void *,const void *)) { long i; (*rozm)=wlk; for(i=wlk/2;i>=1;i--) heapify(tablica,i,wlkEl,(*rozm),porownanie); } /* heapSort. Parameters: - tablica - array of elements, - wlk - number of elements, - porownanie - comparison function, - wlkEl - size of element. */ void heapSort(void *tablica, size_t wlk, const size_t wlkEl, int (*porownanie)(const void *,const void *)) { register long i=0; register char *pierwszy = (char *)tablica; unsigned long rozm=0; if( wlk == 0 || wlk == 1 || wlkEl == 0 ) return; /** TFirst we build heap. */ pierwszy -= wlkEl; buildHeap(pierwszy, wlk, wlkEl, &rozm, porownanie); /* Swaps first with last and build heap. */ for (i=wlk;i>=2;i--) { SWAP(pierwszy+wlkEl, (pierwszy+i*wlkEl), wlkEl); rozm--; heapify(pierwszy, 1, wlkEl, rozm, porownanie); } }