PDA

Visualizza la versione completa : [C] QuickSort


keykode20
06-02-2012, 14:57
ciao a tutti
stavo implementando un quick sort in C il codice perfetto ma dopo aver eseguito e inserito i valori in input il programma non mi restituisce l output, si blocca e va in errore (chiedendomi di inviare segnalazioni).
non capivo dov'era l errore e ho messo dei printf("") spia per capire qual' la parte che creava il problema.



#include <stdio.h>
#define N 5
void quicksort(int a[N], int p, int r){
printf("invocazione riuscita \n");
int q;
if(p<=r){
printf("primo if valutato\n");
q=partition(a,p,r);
printf("partition eseguito\n");
quicksort(a,p,q-1);
printf("lancio quicksort");
printf("prima ricorsione riuscita\n");
quicksort(a,q+1,r);
printf(" seconda ricorsione riuscita\n");
}
}

int partition(int a[N], int p, int r){ //CREDO CHE IL PROBLEMA SIA QUA
int x;
int i;
int j;
x=a[r];
i=p-1;
for(j=0; j<N; j++){
if(a[j]<=x){
i=i+1;
int temp=i;
a[i]=a[j];
a[j]=a[temp];
}
}
int temp1=i+1;
a[i+1]=a[r];
a[r]=a[temp1];
return i+1;
}

void stampa(int a[N]){
int i;
for(i=0; i<N; i++)
printf("%d",a[i]);
}

main(){
int a[N];
int i;
for(i=0; i<N; i++){
scanf("%d",&a[i]);
}
printf("ok\n\n");
quicksort(a,1,N);
stampa(a);
system("PAUSE");
}


stampa all infinito solo "invocazione riuscita" "primo if valutato" e "partition eseguito", non esce mai da partition, sto cercando di mettere altre spie ma da un p che ci sbatto la testa e non arrivo alla conclusione, qualcuno sa darmi una mano?
grazie mille!

ramy89
06-02-2012, 15:16
Nel main chiami:



quicksort(a,1,N);


Nel quicksort:



q=partition(a,p,r); // con r uguale all' N dello scope del main


Nella partition:



x=a[r]; // con r uguale all' r dello scope del quicksort, per cui uguale a 5


Ma vai fuori dall' indice dell' array.
Non so poi se ci sono altri errori, intanto prova a correggere questo.

PS:Spero non sia errato lo pseudocodice o l' algoritmo che stai seguendo.

keykode20
06-02-2012, 17:32
la situazione non cambia, teoricamente lo pseudocodice giusto...
forse dovrei creare un secondo array dove memorizzare i valori che ritornano da partition... magari cambiando il quick sort da void ad un array int. grazie per l aiuto! ^^

ramy89
06-02-2012, 18:10
Nella partition,invece di :



for(j=0; j<N; j++){...}


Non ci dovrebbe essere:



for(j=p;j<r;j++){...}


?

ramy89
06-02-2012, 18:15
Inoltre non effettuavi correttamente lo swap degli elementi, ho corretto il codice:



#include <stdio.h>
#define N 5

int partition(int a[N],int p,int r);
void quicksort(int a[N],int p,int r);

void quicksort(int a[N], int p, int r){
int q;
if(p<=r){
q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}

int partition(int a[N], int p, int r){
int x;
int i;
int j;
x=a[r];
i=p-1;
for(j=p; j<r; j++){ // qua era sbagliato ***********
if(a[j]<=x){
i=i+1;
int temp=i;
a[i]=a[j];
a[j]=a[temp];
}
}
int temp1=a[i+1];
a[i+1]=a[r]; // anche qua ************
a[r]=temp1;
return i+1;
}

void stampa(int a[N]){
int i;
for(i=0; i<N; i++)
printf("%d",a[i]);
}

int main(){
int a[N];
int i;
for(i=0; i<N; i++){
scanf("%d",&a[i]);
}
printf("ok\n\n");
quicksort(a,1,N-1);
stampa(a);
return 0;
}


Tu invece hai scritto :


int temp1=i+1;
a[i+1]=a[r];
a[r]=a[temp1];

Ma in temp1 memorizzavi solo l' indice, non il valore di a[i+1], poi in a[i+1] si scrivevi a[r], e il valore originario di a[i+1] andava perso.

keykode20
06-02-2012, 20:58
Grazie mille! vero non mi ero accordo dell errore sullo scambio!! grazie ancora!!

Loading