[c] Problema algoritmo Random_Select

[Zagor HW]

Dovrei tradurre in C il pseudocodice dell'algoritmo del random select. Il pseudocodice è questo (è preso dal famoso libro "Introduction to Algorithm"):

RANDOMIZED-SELECT(A, p, r, i)
    if p = r
        then return A[p]
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q - p + 1
    if i = k 
        then return A[q]
    elseif i < k
        then return RANDOMIZED-SELECT(A, p, q - 1, i)
    else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

RANDOMIZED-PARTITION(A, p, r)
 	i = RANDOM(p, r)
	exchange(A[r],A[i])
	return PARTITION(A, p, r)

PARTITION(A, p, r)
 	x = A[r]
 	i = p - 1

 	for j = p to r - 1
 		do if A[j] <= x
 			then i = i + 1
 				 exchange(A[i],A[j])
 	exchange(A[i + 1],A[r])
 	return i + 1

Il codice che ho creato in C è il seguente:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIMENSIONE 5

int rand_select(int vet[DIMENSIONE],int inizio,int fine,int elemento);
int rand_partition(int vet[DIMENSIONE],int inizio,int fine);
int partition(int vet[DIMENSIONE],int inizio,int fine);
int genera_num_casuali(int min,int max);

int main()
{
	/*supponendo che il vettore sia gia stato inserito*/
	int vet[DIMENSIONE]={56,12,58,45,67},inizio=0,fine=1,elemento=0,ris=0;
	ris=rand_select(vet,inizio,fine,elemento);
	printf("l'elemento selezionato e':%d\n",ris);
	//printf("%d",vet[ris]);
	return 0;
}

int rand_select(int vet[DIMENSIONE],int inizio,int fine,int elemento)
{
	int q=0,appoggio=0;
	/*HO PROVATO A TOGLIERE IL CONTROLLO DI LUNGHEZZA 0 FORSE SERVE ANCHE PER LA RICORSIONE, AL MASSIMO LO SI METTE NEL MAIN*/
	if(inizio==fine)
		return vet[inizio];
	/*in q viene messa la posizione del pivot, dopo aver applicato
	  la funzione partition*/
	q=rand_partition(vet,inizio,fine);
	appoggio=q-inizio+1;
	/*se il la posizione dell'elemento da ricercare sta alla sinistra
	  del pivot appena calcolato, ripetiamo la select sulla parte
	  sinistra del vettore, altrimenti su quella destra*/
	if(elemento==appoggio)
		return vet[q];
	if(elemento<appoggio)
		return rand_select(vet,inizio,(q-1),elemento);
		else return rand_select(vet,(q+1),fine,(elemento-appoggio));
}

int rand_partition(int vet[DIMENSIONE],int inizio,int fine)
{
	int appoggio=0,scambio=0;
	/*determinazione del numero casuale*/
	appoggio=genera_num_casuali(inizio,fine);

	/*scambio un elemento scelto a "caso" con l'ultimo dell'array*/
	scambio=vet[fine];
	vet[fine]=vet[appoggio];
	vet[appoggio]=scambio;
	/*ritorno il valore che verra generato dalla partition*/
	return partition(vet,inizio,fine);	
}

int partition(int vet[DIMENSIONE],int inizio,int fine)
{
	int appoggio=0,pivot=0,i=0,j=0;
	
	/*prendiamo l'ultimo elemento come pivot*/
	pivot=vet[fine];
	i=inizio-1;
	/*ciclo che sposta i valori minori o uguli del pivot alla sinistra del pivot stesso*/
	/*e mette quelli maggiori alla sua destra*/
	for(j=inizio;j<(fine-1);++j)
	{
		if(vet[j]<=pivot)
		{
			i++;
			appoggio=vet[j];
			vet[j]=vet[i];
			vet[i]=appoggio;
		}
	}
	/*mettiamo il pivot (che era l'ultimo elemento) nella sua posizione*/
	/*in ogni fase del ciclo era sempre rimasto in fondo, con questa
	  operazione lo mettiamo "al suo posto", cioè tutti i numeri più
	  piccoli gli rimangono sulla sinistra, mentre quelli più grandi
	  sulla destra*/
	appoggio=vet[fine];
	vet[fine]=vet[i+1];
	vet[i+1]=appoggio;
	/*ritorniamo la posizione del pivot*/
	return ++i;
}

int genera_num_casuali(int min,int max)
{
	int numero_casuale;
	int differenza;
	differenza = (max - min) + 1;
	if(differenza!=0)
		numero_casuale = rand() % differenza ;
	numero_casuale = numero_casuale + min ;
	return numero_casuale;
}

Il problema è che selezionando un numero tra l'uno e il tre mi restituisce un valore sbagliato, mentre se provo a selezionare il valore 0 o 4 crasha perché la variabile fine (che indica la dimensione del vettore) arriva a raggiungere il valore -1, e dopo qualche ciclo si va a scrivere in una posizione non corretta.
Potete aiutarmi a trovare l'errore visto che sono giorni che guardo e riguardo ma non lo riesco a trovare?
(Il file .c è in allegato)

Grazie