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.