[Algoritmi] Bandiera tricolore

[stefano8612]

Ciao a tutti, sto studiando il problema della bandiera tricolore e ho capito il procedimento ed il relativo codice:

	/**
	 * Passato un array come parametro, ordina i suoi elementi rispettando lo schema 
    * della bandiera italiana. I colori sono definiti tramite la divisione con modulo:
	 * 	- Verde --> a[0...i - 1]: val % 3 == 0
	 * 	- Bianco --> a[i...j - 1]: val % 1 == 0
	 * 	- Parte da esaminare --> a[j...k]
	 *    - Rosso --> a[k + 1...n - 1]: val % 2 == 0
	 *  
	 *		0         i        j                   k       n
	 *		|_________|________|___________________|_______|
	 *		   verde    bianco      da esaminare     rosso
	 *
	 * @param a array di interi
	 */

public static void separateColors(int[] a) {
		int j = 0;
		int i = 0;
		int k = a.length - 1;
		int temp = 0;
		while(j <= k) {
			if(a[j] % 3 == 0) {
				temp = a[j];
				a[j] = a[i];
				a[i] = temp;
				i++;
				j++;
			}
	   		else if(a[j] % 3 == 1)
	   			j++;
	   		else {
				temp = a[k];
				a[k] = a[j];
				a[j] = temp;
				k--;
	   		}
		}
}

Il prof ha spiegato una ottimizzazione de metodo precedente che in pratica consiste nel non effettuare spostamenti inutili.
Nel caso in cui a[j] è rosso, a[j] viene scambiato con a[k]. Ma se anche a[k] è rosso, allora adesso (dopo aver effettuato lo spostamento), a[j] si trova nella parte giusta mentre a[k] no. a[k] verrà spostato nella parte corretta al passo successivo.
Per evitare questo doppio spostamento il prof introduce un ciclo while interno che finché a[k] è rosso decrementa k.

Poi nelle slide c'è scritto "Attenzione: la condizione del while esterno non viene automaticamente controllata; inoltre in questo caso è necessario fermarsi al passo prima che k oltrepassi j (perché?)".

Appunto, perchè? E dove vuole arrivare con "la condizione del while esterno non viene automaticamente controllata"?

Grazie!

[Giova411]

Prova a guardare la "dispensa di esercizi svolti" qui:
http://www.moreno.marzolla.name/teaching/ASD2013/
Puoi trovare qualcosa di moooolto utile e spiegato bene secondo me.

[stefano8612]

"Giova411":Prova a guardare la "dispensa di esercizi svolti" qui:
http://www.moreno.marzolla.name/teaching/ASD2013/
Puoi trovare qualcosa di moooolto utile e spiegato bene secondo me.

Ciao, grazie per la risposta. Ho visto le dispense con gli esercizi e se non mi sbaglio l'unico esercizio che riguarda la bandiera tricolore è il 3.12 che però non cita la miglioria che dicevo io sopra...

Comunque grazie per quelle dispense, sembrano fatte benissimo!

[vict85]

Prova a fare un esempio con carta e penna e vedi che capirai subito il commento.

[stefano8612]

Con il while esterno ci si ferma già al passo prima che k passa j.. no?

[vict85]

La condizione del while viene controllata solo ad inizio ripetizione e non all'interno. Quindi devi sempre assicurarti di mantenere le condizioni appropriate al suo interno. COmunque se k raggiunge j hai semplicemente finito, insomma il tutto è riordinato.