Consiglio per quicksort

[ZfreS]

Ho implementato questa funzione quicksort ma quando la vado ad usare nel main il programma crasha:

La funzione:

Codice:

void quickSort(int arr[], int inizio, int fine)
{
   int i = inizio, j = fine, tmp;

   int pivot = arr[(inizio + fine) / 2];

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



Nel main:

Codice:

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, 4, 12);
   stampaArray(v, 6);


Il problema lo genera nel main, ma non riesco a capire perchè. Potreste aiutarmi per favore?

[Super Squirrel]

Codice:

quickSort(v, 4, 12);

Sei sicuro?
Distrazione oppure non hai implementato tu la funzione e non sai cosa passargli?

Codice:

int v[]{ 4, 7, 2, 9, 3, 12 };

Si può omettere l'=?

[ZfreS]

Giusto, una mia distrazione, ma il problema non si è risolto.

[Super Squirrel]

Mostra il codice completo.

[ZfreS]

Il codice l'ho gia messo tutto, inoltre si fa uso della funzione per copiare l'array:

Codice:

void stampaArray(int arr[], int l)
{
   for (int i = 0; i < l; i++)
      cout << arr[i] << endl;
}


l è la lunghezza dell'array

[Super Squirrel]

Premesso che non ho controllato la funzione quickSort(), ho provato a compilare il codice e sembra funzionare...

A rischio di essere ripetitivo ti chiedo se puoi postare il codice intero, altrimenti l'unica cosa da fare è analizzare in modo accurato quickSort() alla ricerca di qualche bug, e sinceramente se possibile eviterei.

[ZfreS]

Ilfatto è che la stampaArray, il quicksort e il main sono separati nel mio file, o forse vuoi una cosa del genere :

Codice:

void quickSort(int arr[], int inizio, int fine)
{
   int i = inizio, j = fine, tmp;

   int pivot = arr[(inizio + fine) / 2];

   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, 4, 12);
   stampaArray(v, 6);

   system("pause");
   return 0;
}


Quando mando in esecuzione il programma nella parte dove deve stampare l'array ordinato stampa alcuni valori dell'array ma disordinati e poi gli ultimi due valori a caso pure negativi. Quando chiudo la shell mi dice variable v (l'array) was corrupted. Ogni volta che rieseguo il programma gli ultimi due valori casuali sono diversi. In pratica si genera un'eccezione.

[Super Squirrel]

Si intendo metti tutto in un solo file compilabile, testalo e se crasha riportalo pari pari qui sul forum.

In ogni caso vedo ancora quella riga di codice

Codice:

quickSort(v, 4, 12);

non avevi detto che si trattava di una distrazione e che avevi aggiustato?!
Hai capito perchè è sbagliata quella chiamata a funzione?

A questo punto mi viene da pensare che tu stia solo copiando delle funzioni da internet, ma non sappia come richiamarle nel main da te scritto.

[ZfreS]

No, la mia distrazione consisteva nell'aver omesso l'=, ma a quello non ci ho badato. Perchè è sbagliato? La funzione prende il primo elemento e l'ultimo elemento dell'array, e in questo caso sono proprio il 4 e il 12. O forse dovrei passare gli indici che si riferisco a quei numeri, quindi lo 0 e il 7. In tal caso perchè?

[Super Squirrel]

La funzione prende il primo elemento e l'ultimo elemento dell'array, e in questo caso sono proprio il 4 e il 12.

Al di là del caso specifico non ha nessun senso ragionare in termini di valori... ti faccio un esempio, sia
mostra_array(int v[], unsigned int inizio, unsigned int fine)
una funzione che mostra una sottosequenza di un array.
Ipotizziamo di avere il seguente array:
v = 1 1 1 1 1
e di chiamare la funzione mostra_array(v, 1, 1) passandogli come dici tu il valore del primo e dell'ultimo elemento. A questo punto quale dovrebbe essere l'output?
Ti renderai conto che a differenza degli indici, i valori non rappresentano un'informazione univoca.

O forse dovrei passare gli indici che si riferisco a quei numeri, quindi lo 0 e il 7.

In realtà essendo 6 elementi, gli indici sono 0 e 5.