[C] QuickSort

[keykode20]

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]

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]

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]

Nella partition,invece di :

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

Non ci dovrebbe essere:

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

?

[ramy89]

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]

Grazie mille! è vero non mi ero accordo dell errore sullo scambio!! grazie ancora!!