QUICKSORT malfunzionante

di il
3 risposte

QUICKSORT malfunzionante

Avevo chiesto inserendomi in un altro thread ma non ho ricevuto risposta quindi...

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?il problema deve essere per forza nella funzione ricorsiva quicksort,quindi concentratevi lì...perchè funziona solo con alcuni input!

#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;
}

3 Risposte

  • Re: QUICKSORT malfunzionante

    Le correzioni in rosso

    int i = inf,j = sup,pivot =
  • Re: QUICKSORT malfunzionante

    Ora funziona!
    ma come è possibile?
    non è uguale fare pivot = (inf + sup) /2 e poi confrontare con vet[pivot] ?
  • Re: QUICKSORT malfunzionante

    Sarebbe uguale se non spostassi mai l'elemento in posizione (inf+sup)/2. Dato che, però, ciò non è garantito (in quanto è falso che vet < pivot), allora durante l'esecuzione potresti considerare un nuovo pivot, che sarebbe un errore. Con le modifiche suggerite da oregon invece si risolve questo problema
Devi accedere o registrarti per scrivere nel forum
3 risposte