PDA

Visualizza la versione completa : [C++] Randomized Quicksort: a volte ordina, a volte no


francydev
16-11-2010, 19:25
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
17-11-2010, 14:38
Uhm, l'algoritmo è giusto e il codice sembra corretto.
Hai una sequenza di input per la quale il programma non si comporta correttamente?
:ciauz:

francydev
17-11-2010, 22:18
Ho risolto! :D
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
18-11-2010, 14:31
Originariamente inviato da francydev
Ho risolto! :D
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
18-11-2010, 15:43
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
18-11-2010, 15:47
spero che il blu scuro sia perche' hai evidenziato nell'editor. Senno' sei da prendere a scagnate nella schiena :D

MItaly
18-11-2010, 16:17
http://img842.imageshack.us/img842/7067/screenshot1iw.png

Ippo343
18-11-2010, 22:43
Bello, che editor è?

MItaly
18-11-2010, 23:02
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 (http://img152.imageshack.us/img152/3679/schermatax.png)).

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. :)
http://img694.imageshack.us/img694/2153/screenshot1pg.png

Loading