Soluzione 6.7

Ecco la classe SortedArray (piu` sotto si trova la classe IntSorter).
Notare che i metodi scritti rispettano le richieste fatte rispetto ai tempi di esecuzione. Notate in particolare che
import java.util.NoSuchElementException;

public class SortedArray
{   
    /*
        Crea un oggetto OrderedArray vuoto  
    */
    public SortedArray()
    {   array = new int[1];
        arraySize = 0;
    }

    /*
        verifica se l'array e` vuoto. Tempo di esecuzione O(1)
    */
    public boolean isEmpty()
    {   return arraySize == 0;
    }

    /*
        Aggiunge il valore value all'array ordinato, conservando l'ordinamento. 
        Tempo di esecuzione O(n) (prima dell'inserimento l'array e' ordinato!)
    */
    public void add(int value)
    {
        if (arraySize == array.length) // ridimensionamento dell'array. Stavolta
        {                              // non abbiamo usato un metodo ausiliario
            int[] nuovoArray = new int[2 * array.length];
            for (int i = 0; i < arraySize; i++)
                nuovoArray[i] = array[i];
            array = nuovoArray;
        }
        // inserimento e ordinamento dell'array: basta il ciclo interno
        // dell'algoritmo di "ordinamento per inserimento" (Insertion Sort)
        int j;
        for (j = arraySize; j > 0 && value < array[j-1]; j--)
            array[j] = array[j - 1]; 
        array[j] = value;
        arraySize++;
    }
   
    /*
        Cancella il valore massimo dall'array, e lo restituisce. Tempo di
        esecuzione O(1). Lancia NoSuchElementException se l'array e' vuoto
    */
    public int removeMax() throws NoSuchElementException
    {
        if (isEmpty())
            throw new NoSuchElementException();
        arraySize--;   //sfruttiamo il fatto che l'array e` ordinato!
            return array[arraySize];
    }

    /*
        Restituisce la media (average) dei valori dell'array. 
        Tempo di esecuzione O(n)
    */
    public double avg()
    {
        int somma = 0;
        for (int i = 0; i < arraySize; i++)
            somma += array[i];
        return somma / (double) arraySize;
    }

    /*
        Cerca un numero value nell'array ordinato (ricerca binaria). Tempo di
        esecuzione O(log n). Restituisce l'indice nell'array dell'intero value 
        se questo viene trovato, altrimenti restituisce il valore -1
    */
    public int search(int value)
    {
        int da = 0;
        int a = arraySize - 1;
        while (da <= a)
        {
            int medio = (da + a) / 2;
            if (value == array[medio])
                return medio;
            else if (value < array[medio])
                a = medio - 1;
            else
                da = medio + 1;
        }
        return -1;
    }

   private int[] array;
   private int arraySize;

}

La classe IntSorter. Abbiamo usato il metodo Math.random per creare numeri interi pseudo-casuali.
Notare come e` stata realizzata la scrittura su file dei valori dell'array: abbiamo sfruttato le proprieta` della classe SortedArray e del metodo removeMax per scrivere i valori in sequenza ordinata.
import java.io.FileWriter;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.FileNotFoundException;

import java.util.Scanner;

public class IntSorter
{
    public static void main(String[] args) throws IOException
    {
        // gestione argomenti da riga di comando
        if (args.length != 2)
        {   System.out.println("$java IntSorter < numintero > < nomefile >");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);
        if (n < 1)
        {
            System.out.println("La dimensione deve essere > 0");
            System.exit(1);
        }

        //creazione array, inserimento di numeri casuali nell'array
        SortedArray a = new SortedArray();
        for (int i = 0; i < n; i++)
        {
            int k = (int)( n*Math.random());
            a.add(k);
        }

        // stampa della media
        System.out.println("La media dei valori nell'array e`: " + a.avg());

        // ciclo di ricerca di valori nell'array (non abbiamo gestito eccezioni)
        Scanner in = new Scanner(System.in);
        boolean done = false;
        while (!done)
        {
            System.out.print("Valore da cercare (Q per uscire)?: ");
            String cmd = in.nextLine();
            if (cmd.equalsIgnoreCase("Q"))
                done = true;
            else
            {   int value= Integer.parseInt(cmd);
                int j = a.search(value);
                if (j < 0)
                    System.out.println(value + ": non presente");
                else
                    System.out.println(value + ": trovato in indice " + j);
            }
        }

        // scrittura dei numeri in ordine decrescente nel file di output
        PrintWriter writer = new PrintWriter(args[1]);
        final int NUMERI_PER_RIGA = 10;
        int largColonna = args[0].length() + 1;
        int count = 1;
        while (!a.isEmpty())
        {
            String str = Integer.toString(a.removeMax());
            while (str.length() < largColonna)
                str = " " + str;
            if ((count % NUMERI_PER_RIGA) == 0)
                str = str + "\n";
            writer.print(str);
            count++;
        }
        writer.close();
        System.out.println("Scritto contenuto dell'array nel file " + args[1]);
    }
}