Consiglio per quicksort

[oleg.fresi]

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

La funzione:

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:

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?

[oleg.fresi]

Prova così. Che ide usi?

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

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

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 v3[]={ 4, 7, 2, 9, 3, 12 };
	cout << "Ecco l'array disordinato: " << endl;
	stampaArray(v3, 6);
	cout << "Ecco l'array ordinato con quick sort: " << endl;
	quickSort(v3, 0, 5);
	stampaArray(v3, 6); 

	system("pause");
	return 0;
}

[Super Squirrel]

Perfetto, ora compila!

Qualche osservazione:
- le librerie cstdlib e string non servono;
- stesso discorso per il system(pause) e il return 0 se utilizzi un IDEcente;
- ti consiglio di usare sempre le parentesi graffe anche se il while o l'if di turno prevedono un'unica istruzione.

In ogni caso a me il programma sembra funzionare.
Per capire il "problema" che riscontri, e che magari non riesco a riprodurre anche sul mio pc, l'unica soluzione è, come già detto invano più volte, quella di riportare qui sul forum l'output che ricevi dal programma e l'output che invece ti aspetteresti.

[oleg.fresi]

In realta ho sbagliato una cosa nel codice che ho inviato : ho commentato quell'istruzione. Ti prego ti ricopiare il codice corretto dal post precedente e di ricompilarlo.

[Super Squirrel]

Il mio precedente post era già riferito al codice con quella riga decommentata.

Per l'ennesima volta, ma forse parlo arabo... riporta qui sul forum l'output che ricevi dal programma e l'output che invece ti aspetteresti.

[oleg.fresi]

Io mi aspetterei che ad ogni chiamata ricorsiva della funzione quickSort venga stampato quel cout, ma quel che succede dopo aver chiamato nel main la funzione stampaArray, che dovrebbe stampare l'array gia ordinato prima dalla chiamata al quickSort, mi stampa questi valori: 2 9 4 9 2 3 4 7 9 12. Continuo a non capire perchè la stampa del pivot che ogni ad ogni divisione viene cambiato, influenza la stampa dell'ordine corretto degli elementi dell'array.

[Super Squirrel]

Vabbè, speravo che ti saresti accorto da solo che in realtà non c'è nulla di anomalo, ma arrivati a questo punto mi arrendo... prova a lanciare il seguente codice quasi identico al tuo:

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

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

void quickSort(int arr[], int inizio, int fine)
{
   int i = inizio, j = fine, tmp;
   int pivot = arr[(inizio + fine) / 2];
   cout << "pivot: " << 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 v3[]={ 4, 7, 2, 9, 3, 12 };
   cout << "Ecco l'array disordinato: " << endl;
   stampaArray(v3, 6);
   quickSort(v3, 0, 5);
   cout << "Ecco l'array ordinato con quick sort: " << endl;
   stampaArray(v3, 6);

   system("pause");
   return 0;
}

[oleg.fresi]

Si, in effetti l'array veniva stampato correttamente e i valori di pivot erano i primi, anche se non me lo sarei aspettato. Pensavo che sarebbero stati stampati in mezzo ai valori ordinati dell'array. Ti ringrazio ancora per l'aiuto.