HELP!! QUICK-SORT

di il
22 risposte

HELP!! QUICK-SORT

Sto cercando di creare, nel linguaggio C, il programma quick-sort in maniera ricorsiva.
Ho scritto il codice e a livello logico mi torna tutto solo che quando faccio partire il programma mi fa solo aggiungere gli elementi all'array e poi mi da errore...

il codice è il seguente:
#include <stdio.h>
void quicksort (int a[],int p,int r);
void partition (int a[],int p,int r);

int main () {
	int i;
	int *a;
	int n;
	printf ("quanti posti ha l'array? ");
	scanf ("%d",&n);
	a=(int*)malloc(n*sizeof(int));
	for (i=0; i<n; i++) {
		printf ("al posto %d = ",i+1);
		scanf ("%d",&a[i]);
	}
	printf ("\n\n--------------------\n\n");
	quicksort (a,0,n);
	for (i=0; i<n; i++) {
		printf ("ORA al posto %d = %d",i+1,a[i]);
	}
return main();
}

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

void partition(int a[],int p,int r) {
	int x=a[r];
	int t=p-1;
	int temp;
	int j;
	int q;
	for (j=p; j<r-1; j++) {
		if (a[j]<=x) {
			t++;
			temp=a[t];
			a[t]=a[j];
			a[j]=temp;
		}
	}
	temp=a[t+1];
	a[t+1]=a[r];
	a[r]=temp;
return t+1;
}
dove ho sbagliato??

22 Risposte

  • Re: HELP!! QUICK-SORT

    Se lo avresti in c++ ti avrei dato una mano ma mo ci provo
  • Re: HELP!! QUICK-SORT

    O visto da quel poco che so del C sembra giusto
  • Re: HELP!! QUICK-SORT

    Nella funzione quicksort utilizzi la variabile q senza averla inizializzata.
    Comunque per il codice in questione non è che cambi molto tra C e C++ eh, si tratta di una malloc e di printf/scanf invece di cout/cin
  • Re: HELP!! QUICK-SORT

    tuixte ha scritto:


    Nella funzione quicksort utilizzi la variabile q senza averla inizializzata.
    q deve essere uguale a "t+1" come ho scritto nel void "partition" come faccio a riportare quel valore che cambia ad ogni ricorsione nel void "quick-sort"??
  • Re: HELP!! QUICK-SORT

    E' una cosa che hai già fatto.. Partition ritorna t-1, dunque semplicemente fai q = partition(...). Ricorda che dichiarare due variabili in due funzioni diverse, anche se hanno lo stesso nome, significa di fatto creare due variabili differenti.
  • Re: HELP!! QUICK-SORT

    Si ho visto l'errore andava messo come hai detto, solo che quando vado a compilarlo con codeblocks mi da errore:

    error: void value not ignored as it ought to be

    (in aggiunta a prima per chi avesse in futuro questo problema)
    Ho risolto!!! Ho cambiato il "partitiom" da void a int ed ha funzionato solo che non sò il perchè...cioè ho idea che sia per il fatto che dichiarando prima "partition" come void non poteva assegnare un valore numerico a "q"...la mia idea è giusta o sono proprio fuori strada?? ahahaha
  • Re: HELP!! QUICK-SORT

    Ancora non vuole mollare questo dannato programma...
    Allora l'ho compilato, carico l'array e poi mi da un array parzialmente ordinato dove:
    -se l'array è dispari mi mette tutto in ordine solo che fa sparire il numero massimo inserito nell'array mettendo al primo posto zero

    -se l'array è pari peggio ancora, il secondo numero più piccolo sparisce il terzultimo e penultimo si scanbiano di posto (cioè il massimo va al terzultimo mentre il secondo massimo va al penultimo posto) e all'ultimo posto c'è un numerone (che penso sia una posizione)

    Vi prego aiutatemi sto sclerando
  • Re: HELP!! QUICK-SORT

    q=partition(a,p,r);
    Partition è una funzione di tipo void ma che ritorna qualcosa.
    Inizia a fare il debug del codice.
  • Re: HELP!! QUICK-SORT

    maffo95 ha scritto:


    Ho cambiato il "partitiom" da void a int ed ha funzionato solo che non sò il perchè
    Sapere come funzionano le funzioni (scusa il gioco di parole) è la base, non puoi pensare di scrivere un programma senza sapere cosa succede se cambi il tipo di ritorno di una funzione
  • Re: HELP!! QUICK-SORT

    Ragazzi io ho un problema simile!
    ho implementato un quick sort ma non funziona,concettualmente mi sembra giusto sto uscendo pazzo!
    non dà errori ma se visualizzo il vettore dopo la funzione è ancora disordinato
    mi ci date un'occhiata per favore?
    
    #include <stdio.h>
    #define size 10
    #include <stdlib.h>
    #include <time.h>
    
    main()
    {
       int vet[size];
       int i;
       void visualizza(int []);
       int cmp(const void *, const void *);
       void quicksort(int [],int,int);
    
       printf("programma che implementa un ordinamento quicksort su un vettore\n");
       printf("Ecco il vettore iniziale: \n");
       for (i=0; i < size; i++)
          vet[i] = rand() % 200;  //riempie il vettore
       visualizza(vet);   //lo visualizza disordinato
       quicksort(vet,0,size-1);  // richiama la funzione ricorsiva quicksort
       printf("\n\nEcco il vettore ordinato :\n");
       visualizza(vet);
    
       return 0;
    }
    
    void visualizza(int vet[size])
    {
       int i;
    
       for(i=0; i < size; i++)
       {
          if( i % 10 == 0)
              printf("\n");
          printf("%5d",vet[i]);
       }
    }
    
    void quicksort(int vet[size],int inf,int sup)
    {
       void swap(int *, int *);
       int i = inf,j = sup,pivot = (inf+sup)/2;
    
       while(i <= j)
       {
          while( vet[i] < vet[pivot])
             i++;
          while (vet[j] > vet[pivot])
             j--;
          if (i <= j)
          {
             swap(&vet[i],&vet[j]);
             i++;
             j--;
          }
       }
       if  (inf < j)
          quicksort(vet,inf,j);
       if (i < sup)
          quicksort(vet,i,sup);
    }
    
    void swap(int *a,int *b)
    {
       int temp;
    
       temp = *a;
       *a = *b;
       *b = temp;
    }
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  • Re: HELP!! QUICK-SORT

    Si capito devo rivederle un po' queste cose...ripeto che sono alle prime armi (neanche un mese che lo studio) per di più autodidatta...comunque grazie dei vari suggerimenti

    Solo che rimane il fatto che nel mio codice c'è un errore "logico" e non di come è scritto perchè compilarlo me lo compila senza nessun errore solo che il programma non fa il suo dovere diciamo ahaha
    Quindi ripeto: dove sta il mio errore??
  • Re: HELP!! QUICK-SORT

    Beh innanzitutto il main non può terminare con "return main()", altrimenti non termina più il programma! Prova a modificare quello intanto


    Sent from my iPhone using Tapatalk
  • Re: HELP!! QUICK-SORT

    Ovviamente non è quello...quello è per fare varie prove prima di completare al 100% il programma, non influisce sulla sua funzionalità.
  • Re: HELP!! QUICK-SORT

    Beh non conta, è una chiamata ricorsiva che va avanti all'infinito, quindi è un errore
Devi accedere o registrarti per scrivere nel forum
22 risposte