[JAVA]: Problemi di ordinamento con Merge Sort

[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 {
	
	/* Variabili */
	public static String matricola = "800326";
	
	/* 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];
	}
}

[ascatem2]

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

inf è sempre 0???

e poi, io non userei sup, ma testo.length e metterei uan condizione diversa nell'if in modo da non usare quel return abominevole


if (sup >= 2)
mergeSort(testo, inf, testo.length);

detto ciò potresrti farmi un esempio di come dovrebbee essere usato l'algoritmo? coswì lo provo a testare e vedo dov'è il problema.

[pumax84]

Ciao ascatem!

Originariamente inviato da ascatem2

inf è sempre 0???

No, solo la prima volta quando si richiama dal main (che ti posterò nel seguito) la prima volta il metodo OrdinaCrescente.

Originariamente inviato da ascatem2
e poi, io non userei sup, ma testo.length

Beh, ma sup è comunque una variabile ausiliaria con assegnato il valore di testo.length.

Originariamente inviato da ascatem2
e metterei uan condizione diversa nell'if in modo da non usare quel return abominevole

if (sup >= 2)
mergeSort(testo, inf, testo.length);

Si, ma se poi sup è minore di due? Che fa? Almeno con il return esce tranquillo tranquillo dal metodo.

Originariamente inviato da ascatem2
detto ciò potresrti farmi un esempio di come dovrebbee essere usato l'algoritmo? coswì lo provo a testare e vedo dov'è il problema.

Ecco qui la classe di test:

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

La classe di test deve rimanere per forza in questo modo, non posso modificarla.
Ciauz e grazie per l'aiuto.

[pumax84]

Trovato qualcosa???

[alka]

Originariamente inviato da 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?

Ho spostato la discussione nel forum dedicato a Java.
In futuro, poni qui le tue domande relative a questo linguaggio.

Ciao!

[pumax84]

Ti ringrazio alka!

[pumax84]

Niente ragazzi? Nessun'altra idea?

[ascatem2]

penso che uno dei problemi sia che tu inf non lo modifichi mai.

[pumax84]

Si, questo è un altro problema infatti. L'eccezione l'ho risolta sostituendo nell'if "(sup-inf < 2)" al posto di "sup < 2". Ora però non mi ordina in modo corretto, infatti credo sia un problema dell'inf. Dovrei modificarlo inserendo "inf = testo.lenght-sup" mi sa...

[ascatem2]

Originariamente inviato da pumax84
Si, questo è un altro problema infatti. L'eccezione l'ho risolta sostituendo nell'if "(sup-inf < 2)" al posto di "sup < 2". Ora però non mi ordina in modo corretto, infatti credo sia un problema dell'inf. Dovrei modificarlo inserendo "inf = testo.lenght-sup" mi sa...

ma io proprio mi domandavo se eri obbligato a usar eil merge sort...altrimenti usavi il quicksort che prob c'è già un qualche metodo java che lo fa...