Consiglio per quicksort

[ZfreS]

Ah ok, adesso ho capito perchè, m si può implementare un sistema in modo che l'utente inserisca proprio il primo e l'ultimo valore dell'array ma questi vengano poi associati agli indici e l'algoritmo lavora solo con gli indici?

[vict85]

Ah ok, adesso ho capito perchè, m si può implementare un sistema in modo che l'utente inserisca proprio il primo e l'ultimo valore dell'array ma questi vengano poi associati agli indici e l'algoritmo lavora solo con gli indici?

Come ti ha scritto Super Squirrel, i valori non sono necessariamente univoci, quindi la funzione in sé ha poco senso. L'implementazione di una cosa del genere è piuttosto semplice, ma non te lo mostro perché ritengo che sia una pratica poco sicura (se l'elemento non è presente nell'array cominci a leggere memoria a caso finché il tuo programma non crasha, o peggio). Detto questo, che problema stai cercando di risolvere?

[ZfreS]

Perfetto, non ci sono altri problemi oltre questo, grazie mille per l'aiuto!

[ZfreS]

Riprendo un attimo questo thread per un altro dubbio: se chiedo di stampare il pivot dopo averlo calcolato, mi tampa l'array in disordine e non in ordine.Come mai? Il codice è così:

Codice:

void quickSort(int arr[], int inizio, int fine)
{
   int i = inizio, j = fine, tmp;
   int pivot = arr[(inizio + fine) / 2];
       cout << pivot << endl;

   while (i <= j)
   {
      while (arr[i] < pivot)
         i++;           
      while (arr[j] > pivot)
         j--;

         if (i <= j)
         {
         tmp = arr[i];
         arr[i] = arr[j];
         arr[j] = tmp;
         i++;
         j--;
      }
   };

   if (inizio < j)
      quickSort(arr, inizio, j);
   if (i < fine)
      quickSort(arr, i, fine);
}   



[Super Squirrel]

Ma ti riferisci ai valori di pivot oppure alla funzione stampa_array() che richiami alla fine nel main?

[ZfreS]

si è la funzione stampaArray che me li stampa disordinati dopo aver chiamato la mergeSort

[Super Squirrel]

si è la funzione stampaArray che me li stampa disordinati dopo aver chiamato la mergeSort

Sarò sincero, non capisco cosa intendi... cioè prima di aggiungere quel cout << pivot << endl; nella funzione quickSort() il programma funzionava bene?

In ogni caso a scanso di equivoci, metti tutto in un solo file compilabile e riporta il codice qui sul forum insieme a quello che è l'output del programma e l'output che invece ti aspetteresti.

[ZfreS]

Si, prima di mettere il cout funzionava bene, poi no.

[Super Squirrel]

In ogni caso a scanso di equivoci, metti tutto in un solo file compilabile e riporta il codice qui sul forum insieme a quello che è l'output del programma e l'output che invece ti aspetteresti.

[ZfreS]

Codice:

void quickSort(int arr[], int inizio, int fine)
{
   int i = inizio, j = fine, tmp;
   int pivot = arr[(inizio + fine) / 2];
   //cout << pivot << endl;

   while (i <= j)
   {
      while (arr[i] < pivot)
         i++;           
      while (arr[j] > pivot)
         j--;

         if (i <= j)
         {
         tmp = arr[i];
         arr[i] = arr[j];
         arr[j] = tmp;
         i++;
         j--;
      }
   };

   if (inizio < j)
      quickSort(arr, inizio, j);
   if (i < fine)
      quickSort(arr, i, fine);
} 

int main()
{
   int v[]={ 4, 7, 2, 9, 3, 12 };
   cout << "Ecco l'array disordinato: " << endl;
   stampaArray(v, 6);
   cout << "Ecco l'array ordinato con quick sort: " << endl;
   quickSort(v, 0, 5);
   stampaArray(v, 6);

   system("pause");
   return 0;
}