Forum by laureateci.it
[ Home | REGOLE FORUM | Tutti i blog | Profilo | Registrati | CHAT | Discussioni Attive | Discussioni Recenti | Segnalibro | Msg privati | Sondaggi Attivi | Utenti | Download Informatica | Download ICD | Download TPS | Download Magistrale | Download Specialistica | Giochi | Cerca nel web | cerca | faq | RSS ]
Nome Utente:
Password:
Salva Password
Password Dimenticata?

 Tutti i Forum
 ITPS - Primo Anno
 Laboratorio di informatica
 Esercitazione 4 [Insert e Bubble] HELP!!
 Nuova Discussione  Rispondi
 Versione Stampabile Bookmark this Topic Aggiungi Segnalibro
I seguenti utenti stanno leggendo questo Forum Qui c'è:
Autore Discussione Precedente Discussione Discussione Successiva  

Chloe
Utente giovane

Homer


Regione: Puglia
Prov.: Bari
Città: Andria


Inserito il - 15/04/2010 : 17:44:23  Mostra Profilo  Visita l'Homepage di Chloe  Clicca per vedere l'indirizzo MSN di Chloe Invia a Chloe un Messaggio Privato  Rispondi Quotando
Salve ragazzi vorrei un aiutino per implementare il metodo sort() della classe InsertSort utilizzando il metodo swap(int i, int j).

Questa è l'implementazione che so fare io, ma non so metterci lo swap.
	public void sort() {
		for(int i = 1; i < a.length; i++){
			String next = a[i];
			/*
			 * Cerca la posizione in cui inserire, spostando in posizione di
			 * indice superiore a tutti gli elementi di valore maggiore.
			 */
			int j = i;
			boolean isBigger = a[j - 1].compareToIgnoreCase(next) > 0;
			while((j > 0) && isBigger){
				a[j] = a[j - 1];000
				j--;
			}
			a[j] = next;
		}
	}


Per chi non sta frequentando il laboratorio, il metodo swap da utilizzare è questo:
/**
     * Scambia i valori delle stringhe corrispondenti agli indici in input.
     * Inoltre aggiorna gli array directIndexes e invertedIndexes. In questo
     * modo, se gli algoritmi di ordinamento usano questa funzione per
     * scambiare gli elementi dell'array di stringhe, è garantito che anche gli
     * indici riflettono l'effetto dello scambio.
     * 
     * @param i indice (int) della posizione della prima stringa
     * @param j indice (int) della posizione della seconda stringa
     */
    protected void swap(int i, int j) {
    	String strTemp = strings[i];
    	strings[i] = strings[j];
    	strings[j] = strTemp;
    	
    	int indTemp = invertedIndexes[i];
    	invertedIndexes[i] = invertedIndexes[j];
    	invertedIndexes[j] = indTemp;
    	
    	directIndexes[invertedIndexes[i]] = i;
    	directIndexes[invertedIndexes[j]] = j;
    }


è necessario utilizzare questo metodo all'interno del sort() in quanto è importante aggiornare gli indici.
Qualcuno sa darmi una dritta in merito??

Un'altra cosa invece per quanto riguarda il Bubble, qualcuno mi dice se c'è qualche errore in questa implementazione? Come potrei fare per evitare quell'istruzione di break?
	public void sort() {
		for (int i = 0; i < a.length; i++) {
	        boolean flag = false;
	        for (int j = 0; j < a.length - 1; j++) {
	            /*
	             * Se l' elemento j e maggiore del successivo allora
	             * scambiamo i valori
	             */
	             if (a[j].compareToIgnoreCase(a[j + 1]) > 0) {
	                 swap(j, j + 1);
	                 flag = true; 	//Scambio avvenuto con successo
	             }
	         }
	         /*
	          * Se flag = false allora nell' ultima iterazione
	          * non ci sono stati scambi, quindi il metodo può terminare
	          * poiché l' array risulta ordinato
	          */
	         if (!flag) {
	          	break; 
	         }
	    }                 
	}


Grazie a chiunque sia così caritatevole da indirizzarmi sulla strada giusta ^_^

Garet Jax
Utente medio


Regione: Puglia
Prov.: Foggia
Città: San Severo


Inserito il - 16/04/2010 : 02:18:28  Mostra Profilo  Visita l'Homepage di Garet Jax Invia a Garet Jax un Messaggio Privato  Rispondi Quotando
Allora premettendo che l'insertion sort è un algoritmo che non utilizza scambi, ho cercato di usare lo scambio ed allo stesso tempo di mantenere intatto lo spirito dell'algoritmo, ora funziona così:

-Trova la posizione in cui deve andare l'elemento e lo scambia con l'elemento in quella posizione.
-Memorizza quest'ultimo elemento.
-Scala tutti gli elementi successivi.
-Inserisce l'elemento memorizzato nella posizione in cui si trovava prima + 1.

Dato l'orario non so se funzioni o meno o se il ragionamento va bene visto che non l'ho testato.

public void sort() {
for(int i = 1; i < a.length; i++){
/*
* Cerca la posizione in cui inserire, spostando in posizione di
* indice superiore a tutti gli elementi di valore maggiore.
*/
int j = i;
boolean isBigger;
while((j > 0) && isBigger = a[j - 1].compareToIgnoreCase(a[i]) > 0) {
j--;
}
String next = a[j];
swap(i, j);

while (j + 1 < i) {
a[i] = a[i-1];
i--;
}
a[j + 1] = next;
}
}


Per quanto riguarda la seconda....

public void sort() {

boolean flag;
while (!flag)
flag = false;
for (int j = 0; j < a.length - 1; j++) {
/*
* Se l' elemento j e maggiore del successivo allora
* scambiamo i valori
*/
if (a[j].compareToIgnoreCase(a[j + 1]) > 0) {
swap(j, j + 1);
flag = true; //Scambio avvenuto con successo
}
}
/*
* Se flag = false allora nell' ultima iterazione
* non ci sono stati scambi, quindi il metodo può terminare
* poiché l' array risulta ordinato
*/

}
}

In realtà c'è un'altra miglioria che ti permette di evitare di controllare elementi che sono sicuramente nella posizione giusta, ma tant'è
Torna all'inizio della Pagina

vecio88
Utente giovane

1222_da_lacrijux


Regione: Puglia
Prov.: Bari
Città: Bari


Inserito il - 17/04/2010 : 11:22:42  Mostra Profilo  Visita l'Homepage di vecio88  Clicca per vedere l'indirizzo MSN di vecio88 Invia a vecio88 un Messaggio Privato  Rispondi Quotando
Ragazzi ma l'ordinamento è in base alle stringhe o agli indici associati originariamente alle stringhe?

vecio88
Torna all'inizio della Pagina

Chloe
Utente giovane

Homer


Regione: Puglia
Prov.: Bari
Città: Andria


Inserito il - 17/04/2010 : 14:41:12  Mostra Profilo  Visita l'Homepage di Chloe  Clicca per vedere l'indirizzo MSN di Chloe Invia a Chloe un Messaggio Privato  Rispondi Quotando
l'ordinamento è in base alle stringhe.

Grazie mille Garet, l'algoritmo funziona perfettamente.
Torna all'inizio della Pagina
  Discussione Precedente Discussione Discussione Successiva  
 Nuova Discussione  Rispondi
 Versione Stampabile Bookmark this Topic Aggiungi Segnalibro
Vai a:
Forum by laureateci.it © 2002 - 2012 Laureateci Communications Torna all'inizio della Pagina
Il DB ha risposto in 0,74 secondi.

TargatoNA.it | SuperDeejay.Net | Antidoto.org | Brutto.it | Equiweb.it | Snitz Forum 2000