[C] Quick Sort

[dajeroma71]

salve a tutti ho un po di difficolta a creare il main di questo algoritmo di ordinamento....mi potreste aiutare:
la mia funzione di quick sort è la seguente:

void q_s(int x[], int sx, int dx){
		int pivot,i, j, tmp;
		pivot=x[(sx+dx)/2];
		for(i=sx, j=dx; (i<=j);)
			while(x[i]<pivot) i++;
			while(x[j]>pivot) j--;
			if(i<j){
				tmp=x[i];
				x[i]=x[j];
				x[j]=tmp;
			}
			i++;
			j--;
			
}

quando creo il main il compilatore mi dice che devo assegnare dei valore alle varibili dx e sx....quali? questo è il mio main:

int main () {
	int i,n,marray[100],sx,dx;
	printf("inserisci la lunghezza dell'array:");//inserisco di quanti valori è fatto l'array
	scanf("%d", &n);
	for(i=0;i<n;i++){
		printf("inserisci il %d elemento:", i+1); // inserisco i valori nel mio array assegnandoli alle posizioni
		scanf("%d", &marray[i])
	}
	q_s(marray, sx, dx); //richiamo la funzione

	for(i=0;i<n;i++){   // scrivo le posizioni in sequenza
		printf("%d num:", i+1);
		scanf("%d", &marray[i]);
	}	
}

[apatriarca]

È buona norma verificare i valori passati in input. In questo caso n deve essere minore o uguale a 100. In questo programma giocattolo non è molto importante ma nello sviluppo di software reali è abbastanza importante.

sx e dx sono i limiti del tuo array e quindi vanno inizializzati a 0 ed n rispettivamente. Il seguente dovrebbe funzionare correttamente (non ho verificato se c'erano altri errori...):

int main () { 
   int i,n,marray[100]; 
   printf("inserisci la lunghezza dell'array:");//inserisco di quanti valori è fatto l'array 
   scanf("%d", &n); 
   for(i=0;i<n;i++){ 
      printf("inserisci il %d elemento:", i+1); // inserisco i valori nel mio array assegnandoli alle posizioni 
      scanf("%d", &marray[i]) 
   } 
   q_s(marray, 0, n); //richiamo la funzione 

   for(i=0;i<n;i++){   // scrivo le posizioni in sequenza 
      printf("%d num:", i+1); 
      scanf("%d", &marray[i]); 
   }    
}

[dajeroma71]

Io avevo gia provato a fare quello che hai scritto tu...ossia di passare a q_s le posizioni limite del mio array ma il programma loopa.....guarda un po se riesci a scovare l'errore!!te ne sarei molto grato!
ecco il mio programma:

#include<stdio.h>
void q_s(int x[], int sx, int dx);
void stampa(int x[], int N);
int main () { 
   int i,n,marray[100]; 
   printf("inserisci la lunghezza dell'array:");//inserisco di quanti valori è fatto l'array 
   scanf("%d", &n); 
   for(i=0;i<n;i++){ 
      printf("inserisci il %d elemento:", i+1); // inserisco i valori nel mio array assegnandoli alle posizioni 
      scanf("%d", &marray[i]); 
   } 
   q_s(marray, 0, n); //richiamo la funzione 
   stampa(marray, n );
} 



	void q_s(int x[], int sx, int dx){
		int pivot,i,j,tmp;
		pivot=x[(sx+dx)/2];
		for(i=sx, j=dx; (i<=j);)
			while(x[i]<pivot) i++;
			while(x[j]>pivot) j--;
			if(i<j){
				tmp=x[i];
				x[i]=x[j];
				x[j]=tmp;
			}
			i++;
			j--;
			
}
	void stampa(int x[], int N){
		int i;
		for(i=0;i<N;i++){   // scrivo le posizioni in sequenza 
      printf("%d num:", i+1); 
      scanf("%d", &x[i]); 
   }    
	}

[mod="Luc@s"]Usa il tag code. Altrimenti è casinoso leggere[/mod]

[dajeroma71]

nella funzione stampa ho sbagliato una cosa....meglio questa versione!!!hihihi:

void stampa(int x[], int N){ 
    int i;
 
    for(i=0;i<N;i++){ // scrivo le posizioni in sequenza
 
         printf("il % d num è %d:",i+1, x[i] ); 
     }

[apatriarca]

La tua implementazione del quicksort è sbagliata. Prima di tutto mancano le parentesi intorno al ciclo for. Questo risolve il problema del ciclo infinito ma la funzione non ordina comunque correttamente gli array passati. A prima vista direi che manca la chiamata ricorsiva e il tuo codice sembra esclusivamente partizionare l'array. Direi che dovresti ricontrollare che il tuo codice rispetti l'algoritmo che ti è stato dato.

[provola-votailprof]

allora! Va in loop perchè nel for del quick sort non hai messo le parentesi graffe... In ogni caso se le metterai scoprirai che il codice non fa quanto richiesto
Vuoi la soluzione spiattellata così o vuoi provare a farlo tu stesso?
Intanto ti do' un piccolo aiuto...
Prendi questo vettore come esempio:
vettore: 12 32 44 1 23 34 2
indici: 0 1 2 3 4 5 6

tu come pivot scegli l'elemento nel mezzo, scelta discutibile ma non scorretta. per cui in questo caso sarebbe: x[(0+7)/2]=x[3]=1
ora devi scorrere il vettore da sinistra verso destra alla ricerca del primo elemento che supera il pivot e da destra verso sinistra alla ricerca di uno che sia minore o UGUALE.
Per la prima parte troverai il 12 e per la seconda l'1 stesso
Ora dovrai scambiarli (avendo così: 1 32 44 12 23 34 2)
Proseguendo avrai che l'indice i avrà superato l'indice j, poichè il primo elemento maggiore rispetto al pivot sarà il 32 (i=1) mentre il primo elemento minore sarà l'1 (j=0)
A questo punto dovrai considerare i due sottovettori:
primo vettore: 1
secondo vettore: 32 44 12 23 34 2
ed ordinarli sempre mediante quicksort separatamente.
Il primo sottovettore è già ordinato (c'è un solo elemento... ma il calcolatore non ne ha la più pallida idea), il secondo invece no (ma per il calcolatore sempre idem come prima) e dovrai reiterare su entrambi i sottovettori l'algoritmo di quicksort... Quando si finisce?
Buon lavoro

EDIT:
-occhio ai limiti che usi... dx sei sicuro sia uguale ad n?
-è buona norma mettere un bel return 0 se il main lo hai dichiarato come una funzione che restituisce un intero (int main)

[dajeroma71]

Grazie dei chiarimenti zac, guarda un po se puo andare bene...:

#include<stdio.h>
void quick_sort(int x[], int sx, int dx);
void stampa(int x[], int N);
int main () { 
   int i,n,marray[100];
   printf("inserisci la lunghezza dell'array:");//inserisco di quanti valori è fatto l'array 
   scanf("%d", &n); 
   for(i=0;i<n;i++){ 
     printf("inserisci il %d elemento:", i+1); // inserisco i valori nel mio array assegnandoli alle posizioni 
      scanf("%d", &marray[i]); 
   } 
   quick_sort(marray, 0, n-1); //richiamo la funzione 
   stampa(marray, n );
   return 0;
} 

void quick_sort(int x[], int sx, int dx){
	int i,j,tmp,pivot;
	pivot = x[(sx+dx)/2]; 
	for(i=sx, j=dx; (i<j);){ 
		while(x[i]<pivot){
			i++;} 
		while(x[j]>pivot){
			j--;}
	
         if(i<=j){ 
            tmp=x[i]; 
            x[i]=x[j]; 
            x[j]=tmp; 
			
         } 
         i++; 
         j--; 
	}
	       
} 
void stampa(int x[], int N){ 
    int i; 
    for(i=0;i<N;i++){ // scrivo le posizioni in sequenza 
		 printf("il % d num è %d\n:",i+1, x[i] ); 
	} 
}

[Umby2]

"dajeroma7":Grazie dei chiarimenti zac, guarda un po se puo andare bene...:

Ti vorrei consigliare di testare tu stesso il corretto funzionamento del programma.

Potresti, ad esempio, inserire per ogni ciclo di ordinamento una visualizzazione dell'intero vettore, in modo va verificare passo passo se tutto va come deve andare.
Cosi' facendo ti renderai conto di eventuali imperfezioni nel codice.

[dajeroma71]

testato e funzionante...! grazie mille
ora provo con il merge sort mi sa che sentirete ancora parlare di me!
ahahahahahhahaha

[apatriarca]

@ dajeroma7: ma sei certo che funzioni? A me continua a non sembrare un quicksort. Mancano ancora le chiamate ricorsive sulle due partizioni dell'array. Hai testato il programma con un numero sufficiente di casi?

Potresti, ad esempio, inserire per ogni ciclo di ordinamento una visualizzazione dell'intero vettore, in modo va verificare passo passo se tutto va come deve andare.
Cosi' facendo ti renderai conto di eventuali imperfezioni nel codice.

Oppure può usare un buon debugger che gli permetta di farlo senza far ricorso a chiamate alla funzione che stampa il vettore e che gli permette di vedere il funzionamento del suo programma passo-passo.

[provola-votailprof]

ma sei sicuro? perchè "funzionare" funziona, ma non ordina come dovrebbe... con quanti numeri lo hai testato? Io ne ho inseriti 9: 2, 32, 3, 3, 14, 11, 45, 9, 10
e come risultato da' il seguente: 2, 10, 3, 3, 9, 11, 45, 14, 32
Non mi sembra ordinato :/
Se ti interessa il codice corretto te lo posto, se ci vuoi pensare meglio fai tu...

edit: ops stesso consiglio di apatriarca, ma non avevo visto che ti aveva scritto

[dajeroma71]

mmmm avete ragione adesso l'ho testato con un numero maggiore di casi e sembra non funzionare AFFATTO!!!
mi interesserebbe il codice zac...
Pero è possibile scrivere il quick sort fac-simile al mio?
ossia iterativamente e non ricorsivamente?

[provola-votailprof]

uhm... perchè lo vuoi iterativo? È assai più semplice da implementare recursivamente... Cmq ci provo

[dajeroma71]

perche il prof ce li ha chiesti entrambi...comunque quello ricursivo l'ho fatto bastava aggiungere alla fine dell quick_sort:

quick_sort(x,sx,j);
quick_sort(x,i,dx);

in questa maniere è come se dividesse l'array in 2 parti vero? 1 delimitata dall'estremo sx e dal puntatore j e l'altra delimitata dal puntatore i a l'estremo di dx?

[provola-votailprof]

mh... più o meno... lo scambio dovresti farlo solo se i
edit: per il metodo iterativo, sai usare uno stack?

edit2: dai un'occhiata su wikipedia, l'articolo sul quicksort è ben fatto http://it.wikipedia.org/wiki/Quicksort ed ha anche una sezione interamente dedicata al quick sort iterativo con tanto di pseudo codice... non lo implemento io stesso perchè sto uscendo e perchè non so come sei messo con l'uso degli stack