Ciao a tutti, come esercizio cercavo di implementare un quicksort randomized, cercando su internet sono riuscito a trovare lo pseudocodice relativo
codice:
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
codice:
#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.