Newsgroup: it.comp.java
Titolo: Programma e problema in esecuzione

devo scrivere un programma che esegue ordinamenti con mergesort, misuri
tempi di esecuzione e restituisca il numero di visite per ogni confronto
l'algoritmo di ordinamento esegue.
le specifiche mi dicono di usare una classe Comparator che dispone del
metodo compare() che effettua il confronto e il conteggio del numero dei
confronti ad ogni sua invocazione.
il programma viene compilato ma l'interprete mi segnala errore.
ecco le classi e interfaccie:
*Interfaccia* *Comparator* :
public interface Comparator
{ int compare (Object a, Object b);
  int getVisite();
}
*Classe* *DefaultComparator* :
public class DefaultComparator implements Comparator
{  private int numVisite;
   public DefaultComparator()  { numVisite = 0; }
   public int getVisite()  { return numVisite; }
   public int compare(Object a, Object b)
   { numVisite++;
     return ((Comparable)a).compareTo(b);
   }
}
*Classe* *MergeSort* :
public class MergeSort
{ private Object[] v;
  private Comparator c;
  public MergeSort() { c = new DefaultComparator(); }
  public MergeSort(Comparator x)  { c = x; }
  public int getNumVisite()  { return c.getVisite(); }
  public void ordinaMS(Object[] x, int n)
  { v = x;
    MS (0, n-1);
  }
  private void MS(int s, int d)
  { if (s < d)
    { int c = (s + d)/2;
      MS(s, c);
      MS(c+1, d);
      merge(s, d);
    }
  }
  private void merge(int s, int d)
  { Object[] tmp = new Object[d-s+1];
    int i1 = s;
    int d1 = (s + d)/2;
    int i2 = d1 + 1;
    int d2 = d;
    int i = 0;
    while (i1 <= d1 && i2 <= d2)
      if (c.compare(v[i1], v[i2]) < 0)
        tmp[i++] = v[i1++];
      else
        tmp[i++] = v[i2++];
    while (i1 <= d1)
      tmp[i++] = v[i1++];
    while (i2 <= d2)
      tmp[i++] = v[i2++];
    for (i = 0; i < d-s+1; i++)
      v[s+i] = tmp[i];
  }
}
*Classe* *Prova* :
import java.io.*;
import java.util.*;
public class Prova
{ public static void main(String[] arg) throws IOException
  { final int MAX = 1000001;
    String[] dati = new String[MAX];
    QuickSort q;
    MergeSort m;
    HeapSort h;
    System.out.println("Inserire il nome del file di testo con
estensione:");
    BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));
    String nomeFile;
    while ((nomeFile = in.readLine()) != null)
    {  q = new QuickSort();
       m = new MergeSort();
       h = new HeapSort();
       BufferedReader fileDati = new BufferedReader(new
FileReader(nomeFile));
       int n = 0;
       while ((dati[n] = fileDati.readLine()) != null) n++;
       System.out.print("QuickSort: " + nomeFile + " " + n + " stringhe -
");
       long tempo = -System.currentTimeMillis();
       try
       { q.ordinaQS(dati, n);
         tempo += System.currentTimeMillis();
         System.out.println("millisecondi " + tempo + "; numero di visite: "
+ q.getNumVisite());
         for (int i = 1; i < n; i++)
           if (dati[i-1].compareTo(dati[i]) > 0)
             System.out.println("Errore: dati[" + (i-1) + "] = " + dati[i-1]
                                       + ", dati[" + i + "] = " + dati[i]);
       } catch (StackOverflowError e) {System.out.println("RTS overflow");}
       fileDati.close();
    }
  }
}
mi segnala un null pointer exception, a quanto pare al metodo merge.
grazie davvero tanto a chi saprà segnalarmi gli errori :-)

 il programma viene compilato ma l'interprete mi segnala errore.
rettifico:
al posto del mergesort, era HeapSorto
ecco la
*Classe* *HeapSort* :
public class HeapSort
{ private Object[] v;
  private Object[] tmp;
  private Comparator c;
  public HeapSort() { c = new DefaultComparator(); }
  public HeapSort(Comparator x)  { c = x; }
  public int getNumVisite()  { return c.getVisite(); }
  public void ordinaHS(Object[] x, int n)
  { v = x;
    HS (0, n-1);
  }
  private void HS(int s, int d)
  { if (s < d)
    { Object p = v[d];
      int i;
      int l = v.length;
      Object temp;
      for (i = (l/2)-1; i >= 0; i--)
        siftDown(v, i, l);
      for (i = l-1; i >= 1; i--)
      { temp = v[0];
        v[0] = v[i];
        v[i] = temp;
        siftDown(v, 0, i-1);
      }
    }
  }
  private void siftDown(Object[] a, int root, int bottom)
  { boolean done = false;
    int maxChild;
    Object temp;
    while ((root*2 <= bottom) && (!done))
    { if (root*2 == bottom || c.compare(a[root*2], a[root*2 + 1]) > 0)
        maxChild = root*2;
      else
        maxChild = root*2 + 1;
      if (c.compare(a[root], a[maxChild]) < 0 )
      { temp = a[root];
        a[root] = a[maxChild];
        a[maxChild] = temp;
        root = maxChild;
      }
      else
        done = true;
    }
  }
}
la *Classe* *Prova* è questa:
import java.io.*;
import java.util.*;
public class Prova
{ public static void main(String[] arg) throws IOException
  { final int MAX = 1000001;
    String[] dati = new String[MAX];
    HeapSort h;
    System.out.println("Inserire il nome del file di testo con
estensione:");
    BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));
    String nomeFile;
    while ((nomeFile = in.readLine()) != null)
    {  h = new HeapSort();
       BufferedReader fileDati = new BufferedReader(new
FileReader(nomeFile));
       int n = 0;
       while ((dati[n] = fileDati.readLine()) != null) n++;
       System.out.print("QuickSort: " + nomeFile + " " + n + " stringhe -
");
       long tempo = -System.currentTimeMillis();
       try
       { h.ordinaHS(dati, n);
         tempo += System.currentTimeMillis();
         System.out.println("millisecondi " + tempo + "; numero di visite: "
+ h.getNumVisite());
         for (int i = 1; i < n; i++)
           if (dati[i-1].compareTo(dati[i]) > 0)
             System.out.println("Errore: dati[" + (i-1) + "] = " + dati[i-1]
                                       + ", dati[" + i + "] = " + dati[i]);
       } catch (StackOverflowError e) {System.out.println("RTS overflow");}
       fileDati.close();
    }
  }
}
ecco