[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