[C++] Randomized Quicksort: a volte ordina, a volte no

[francydev]

Ciao a tutti, come esercizio cercavo di implementare un quicksort randomized, cercando su internet sono riuscito a trovare lo pseudocodice relativo

Rand-Partition(A, p, r)
i := Random(p, r)
interchange A[i] and A[r]
return Partition(A, p, r)

Rand-Quicksort(A, p, r)
if p < r then
q := Rand-Partition(A, p, r)
Rand-Quicksort(A, p, q − 1)
Rand-Quicksort(A, q + 1, r)

Ora ho provato ad implementare questo in un mio quicksort che già avevo in precedenza, il risultato è stato

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
typedef int Item;
int partition(Item a[], int l, int r);
void swap(Item &A, Item &B);
void compswap(Item &A, Item &B);
void quicksort(int a[],int l, int r);
int randomized_partition(int a[], int l, int r);


int main(){
	
	int numvar;
	cout<<"inserire dimensione dell'array"<<endl;
	cin>>numvar;
	int *a=new int[numvar];
	for(int i=0;i<numvar;i++)
		cin>>a[i];
	quicksort(a,0,numvar-1);
	cout<<"array ordinato:"<<endl;
	for(int i=0;i<numvar;i++){
		cout<<a[i]<<endl;}
	delete []a;
	return 0;

}

int partition(Item a[], int l, int r){
	int i=l-1, j=r;
	Item v=a[r];
	for( ;; ){
		while (a[++i]<v);
		while(v<a[--j]) if(j==l) break;
		if(i>=j) break;
		swap(a[i],a[j]);
	}
	swap(a[i],a[r]);
	return i;
}
void swap(Item &A,Item &B){
	Item t=A;
	A=B;
	B=t;
}
void compswap(Item &A, Item &B){
	if(B>A) swap(A,B);
}
void quicksort(int a[],int l, int r){
	if(r<=l) return;
	int i=randomized_partition(a,l,r);
	quicksort(a,l,i-1);
	quicksort(a,i+1,r);
}
int randomized_partition(int a[], int l, int r){
	srand((unsigned)time(NULL));
	int i=rand()%(r-l+1);
	swap(a[i],a[r]);
	return partition(a,l,r);

}

Il problema è che l'array risultante, a volte è ordinato a volte no, secondo me sbaglio qualcosa con la random. Se qualcuno mi da qualche dritta gliene sarò grato.

[powerweb]

Uhm, l'algoritmo è giusto e il codice sembra corretto.
Hai una sequenza di input per la quale il programma non si comporta correttamente?

[francydev]

Ho risolto!
Come sospettavo il problema nasceva quando andavo a creare l'indice random, ho risolto con questa modifica: int i=l+rand()%(r-l+1);
Ora funziona!

[MacApp]

Originariamente inviato da francydev
Ho risolto!
Come sospettavo il problema nasceva quando andavo a creare l'indice random, ho risolto con questa modifica: int i=l+rand()%(r-l+1);
Ora funziona!

leggibilissimo l'identificatore "l"
ad esempio:

l |= l||1+1*l;

;-)

[MItaly]

Originariamente inviato da MacApp
leggibilissimo l'identificatore "l"
ad esempio:

l |= l||1+1*l;

;-)

Con un font adeguato e la colorazione dei literal la questione diventa sorprendentemente più chiara:

[Mashin]

spero che il blu scuro sia perche' hai evidenziato nell'editor. Senno' sei da prendere a scagnate nella schiena

[MItaly]

[Ippo343]

Bello, che editor è?

[MItaly]

gedit, tema Cobalt, font DejaVu Sans Mono 12 Regular; per piccoli lavori con quello, make, astyle (richiamato con uno shortcut direttamente da gedit) e un terminale me la cavo senza problemi (link).

Un altro tema che stavo valutando era Oblivion, che mi sembra un po' più riposante ma non sono sicuro che mi piaccia troppo; deciderò questa sera.