[Java2] Problemi di ordinamento

[pumax84]

Ciao ragazzi, non capisco perchè mi va in Exception quando richiamo ricorsivamente la funzione mergeSort per ordinare stringhe di testo in ordine lessicografico crescente. Qualche suggerimento?

Ecco il codice:

public class OrdinaTesto {
	
	/* Costruttore */
	public OrdinaTesto() {}
	
	
	/* Metodi */
	public static void ordinaCrescente(String testo[]) {
		int inf = 0;
		int sup = testo.length;
		if (sup < 2) return;
		mergeSort(testo, inf, sup);
	}
	

	public static void mergeSort(String testo[], int inf, int sup) {
		int m = (inf+sup)/2;
		if (sup < 2) return;
		mergeSort(testo, inf, m);
		mergeSort(testo, m+1, sup);
		merge(testo, inf, m, sup);
	}
	
	
	public static void merge(String testo[], int inf, int med, int sup) {
		String testoAux[] = new String[sup-inf+1];
		int i = 0;
		int i1 = inf;
		int i2 = med;
		while(i1 < med && i2 < sup) {
			if(testo[i1].compareTo(testo[i2]) <= 0)
				testoAux[i++] = testo[i1++];
			else
				testoAux[i++] = testo[i2++];
		}
		
		while(i1 < med)
			testoAux[i++] = testo[i1++];
				
		while(i2 < sup)
			testoAux[i++] = testo[i2++];
				
		while(i2 > inf)
			testo[--i2] = testoAux[--i];
	}
}

[pumax84]

Nessuna idea ragazzi?

[sottovento]

Ciao,
ho controllato il codice un po' velocemente, ma mi sembra che la base ricorsiva sia un po' debole. Non vorrei sbagliarmi ne' portarti fuori strada...

Prova a stampare inf e sup per ogni iterazione. Secondo me quando esegui
mergeSort(testo, m+1, sup);
ti trovi a creare un ciclo infinito, visto che non potra' mai essere raggiunta la base della ricorsione (se sup e' > 2 ad una certa chiamata, lo sara' anche alla chiamata successiva)

High Flying
Sottovento

[pumax84]

Originariamente inviato da sottovento

Ciao,
ho controllato il codice un po' velocemente, ma mi sembra che la base ricorsiva sia un po' debole. Non vorrei sbagliarmi ne' portarti fuori strada...

Prova a stampare inf e sup per ogni iterazione. Secondo me quando esegui
mergeSort(testo, m+1, sup);
ti trovi a creare un ciclo infinito, visto che non potra' mai essere raggiunta la base della ricorsione (se sup e' > 2 ad una certa chiamata, lo sara' anche alla chiamata successiva)

High Flying
Sottovento

Ciao, ti ringrazio per la risposta. Comunque il "testo" si dimezzerà di volta in volta perchè oltre alla chiamata mergeSort eseguirà subito dopo per quella chiamata la funzione merge che dividerà e fonderà in seguito ricorsivamente (divide et impera) il testo.
Se intendevi altro sono qui... Grazie ancora!
Ciauz

[sottovento]

Ciao,
beh... intendevo un'altra cosa. Ho letto attentamente la tua risposta e non mi sembra di aver commesso errori. Ovviamente hai passato piu' tempo sul pezzo del sottoscritto, quindi e' immaginabile che mi sia scappato qualcosa, pero'...

	public static void mergeSort(String testo[], int inf, int sup) {
		int m = (inf+sup)/2;
		if (sup < 2) return;
		mergeSort(testo, inf, m);
		mergeSort(testo, m+1, sup);
		merge(testo, inf, m, sup);
	}

Supponi per esempio che in partenza sia sup=4.
Sono d'accordo sul fatto che il testo si dimezza, ma sup non viene piu' ricalcolato, per cui sup=4 per tutta la durata del metodo.
La seconda chiamata ricorsiva (mergeSort(testo, m+1, sup)) avra' ancora sup=4. Non essendo soddisfatta la base della ricorsione (la quale e' sup < 2) chiamera' ancora ricorsivamente, sempre con sup=4. E cosi' via.

Spero di esserti di aiuto e ti chiedo scusa se, a causa di una svista, ti faccio perder tempo.... cmq se ho un po' di tempo (lavoro anche di domenica ) faccio qualche prova

High Flying
Sottovento

[pumax84]

Aaaaah... ora ho capito cosa intendevi.

Quindi dovrei inserire l'istruzione sup = testo.length; anche nel metodo mergeSort oltre all'OrdinaCrescente giusto?

E comunque figurati, non mi stai facendo perder tempo, anzi ti ringrazio per le risposte nonostante tu stia lavorando!

[sottovento]

Originariamente inviato da pumax84

Aaaaah... ora ho capito cosa intendevi.

Quindi dovrei inserire l'istruzione sup = testo.length; anche nel metodo mergeSort oltre all'OrdinaCrescente giusto?

Ehm, dovrei analizzare meglio il problema, ma credo che sia giusto. Comunque ho l'impressione che lo risolverai nei prossimi 10 minuti... credo che tu sia sulla strada giusta...

Ho anche notato che con la versione da te pubblicata la routine merge() non poteva andare in esecuzione. Forse questo ti puo' essere di aiuto.

High Flying
Sottovento

[pumax84]

Ho provato con l'inserire l'istruzione dove avevo indicato, ma nulla...

In che senso non poteva andare in esecuzione???

Comunque questa è la classe TestOrdinaTesto.class che non posso purtroppo modificare:

import java.io.*;
import java.util.Scanner;
import java.util.Vector;

public class TestOrdinaTesto
{

    public TestOrdinaTesto()
    {
    }

    public static void main(String args[])
    {
        if(args.length == 1)
        {
            Scanner scanner = null;
            String s = args[0];
            try
            {
                scanner = new Scanner(new FileReader(s));
            }
            catch(FileNotFoundException filenotfoundexception)
            {
                System.out.println((new StringBuilder()).append("Eccezione FileNotFoundException nell'apertura in lettura del file ").append(s).toString());
                filenotfoundexception.printStackTrace();
                System.exit(1);
            }
            scanner.useDelimiter("\\n");
            Vector vector = new Vector();
            for(; scanner.hasNext(); vector.add(scanner.next()));
            scanner.close();
            String args1[] = (String[])vector.toArray(new String[0]);
            long l = System.currentTimeMillis();
            OrdinaTesto.ordinaCrescente(args1);
            l = System.currentTimeMillis() - l;
            PrintWriter printwriter = null;
            try
            {
                printwriter = new PrintWriter((new StringBuilder()).append("sorted.").append(s).toString());
            }
            catch(FileNotFoundException filenotfoundexception1)
            {
                System.out.println((new StringBuilder()).append("Eccezione FileNotFoundException nell'apertura in scrittura del file sorted.").append(s).toString());
                filenotfoundexception1.printStackTrace();
                System.exit(2);
            }
            for(int i = 0; i < args1.length; i++)
                printwriter.println(args1[i]);

            printwriter.close();
            System.out.println((new StringBuilder()).append("tempo = ").append(l).append("msec.").toString());
        } else
        {
            System.out.println("Uso da prompt: java TestOrdinaTesto <nomeFileTesto>; output nel file sorted.<nomeFileTesto>.");
        }
    }
}

[sottovento]

ATTENZIONE - ho controllato un attimino il software: non penso che l'istruzione
sup = testo.length
ti risolva il problema.
Infatti non passi alla funzione delle porzioni del tuo vettore, ma passi il vettore stesso ed i limiti entro cui effettuare le operazioni. Pertanto l'operazione in questione ti riportera' un valore che non e' di tuo interesse.

Scusami se non posso dedicare tanto tempo al problema.
Forse puoi trovare la documentazione e l'algoritmo completo su google, se non altro come riferimento

High Flying
Sottovento

[pumax84]

Ok, ti ringrazio comunque!
Ciauz

[sottovento]

Originariamente inviato da pumax84

Ok, ti ringrazio comunque!
Ciauz

Ciao,
penso che l'istruzione che volevi introdurre fosse:

if ((sup - inf) < 2) return;

cioe' penso che tu voglia controllare che il vettore sia non banale.

Prova con questa al posto di:
if (sup < 2) return;

Per quanto riguarda il resto dell'algoritmo, sembra a posto. Nel caso di problemi, segnala!!!

High Flying
Sottovento

[pumax84]

Ok perfetto, controllo subito, grazie di nuovo!

[pumax84]

Bene, ora non restituisce più eccezione solo che l'ordinamento non avviene in modo corretto, probabilmente è sbagliato qualcosa nel metodo merge().

Ad esempio in un file prova.txt fatto di parole casuali in questo modo:
ciao
pippo
nome
135
256
aaa
zzz
forse
bye

Restituisce il file "teoricamente" ordinato in questo modo:
256
aaa
ciao
forse
bye
nome
135
pippo
zzz



Quindi presumo ci sia qualche errore nel metodo merge()....

[pumax84]

Risolto! Posto il codice completo nel caso fosse utile a qualcun'altro!

Ciauz

public class OrdinaTesto {
	
	/* Costruttore */
	public OrdinaTesto() {}
	
	
	/* Metodi */
	public static void ordinaCrescente(String testo[]) {
		String testoTemp[];
		testoTemp = new String[testo.length];
		mergeSort(testo, testoTemp, 0, testo.length-1);		
	}
	
	public static void mergeSort(String[] testo, String[] testoTemp, int inf, int sup) {
		if(inf == sup) return;
		int m = (inf+sup)/2;
		mergeSort(testo, testoTemp, inf, m);
		mergeSort(testo, testoTemp, m+1, sup);
		merge(testo, testoTemp, inf, m+1, sup);
	}
	
	
	public static void merge(String[] testo, String[] testoAux, int inf, int med, int sup) {
		int endSx = med-1;
        int posAux = inf;
        int numElem = sup-inf+1;
		
		while (inf <= endSx && med <= sup) 
			if(testo[inf].compareTo(testo[med]) <= 0) 
				testoAux[posAux++] = testo[inf++];
			else
				testoAux[posAux++] = testo[med++];
		
		while (inf <= endSx)
			testoAux[posAux++] = testo[inf++];
				
		while (med <= sup)
			testoAux[posAux++] = testo[med++];
				
		for (int i=0; i<numElem; i++,sup--)
			testo[sup] = testoAux[sup];
		
	}
}

[sottovento]

Certamente utile!
Grazie per aver postato il codice

High Flying
Sottovento