Capitolo 16 - di.unito.itdamiani/DIDATTICA/aa03/BI-ProgEAlg/Cap16.pdf©Apogeo 2002 Horstmann...

©Apogeo 2002Horstmann Concetti di informatica e fondamenti di Java 2

1

Capitolo 16 Ordinamento e ricerca

Capitolo 16

Ordinamento e ricerca



2

Capitolo 16 Ordinamento e ricercaFile SelectionSorter.java

/**Questa classe ordina un array,usando l’algoritmo di ordinamento per selezione.

*/public class SelectionSorter{

/**Costruisce un ordinatore per selezione.@param anArray l’array da ordinare

*/public SelectionSorter(int[] anArray){

a = anArray;}

/**Ordina l’array gestito da questo ordinatore.

*/


3

Capitolo 16 Ordinamento e ricercapublic void sort()

{for (int i = 0; i < a.length – 1; i++){

int minPos = minimumPosition(i);swap(minPos, i);

}}

/**Trova l’elemento minimo in una parte terminaledell’array.@param from la prima posizione in a che va

considerata@return la posizione dell’elemento minimo presente

nell’intervallo a[from]...a[a.length – 1]*/


4


private int minimumPosition(int from){

int minPos = from;for (int i = from + 1; i < a.length; i++)

if (a[i] < a[minPos]) minPos = i;return minPos;

}

/**Scambia due elementi nell’array.@param i la posizione del primo elemento@param j la posizione del secondo elemento

*/private void swap(int i, int j){

int temp = a[i];a[i] = a[j];a[j] = temp;

}

private int[] a;}


5

Capitolo 16 Ordinamento e ricercaFile SelectionSortTest.java

/**Questo programma collauda l’algoritmo di ordinamento

per selezione ordinando un array contenente numeri casuali.*/public class SelectionSortTest{

public static void main(String[] args){

int[] a = ArrayUtil.randomIntArray(20, 100);ArrayUtil.print(a);

SelectionSorter sorter = new SelectionSorter(a);sorter.sort();

ArrayUtil.print(a);}

}

6

Capitolo 16 Ordinamento e ricercaFile ArrayUtil.javaimport java.util.Random;

/**Questa classe contiene metodi utili perla manipolazione di array.

*/public class ArrayUtil{

/**Costruisce un array contenente valori casuali.@param length la lunghezza dell’array@param n il numero di valori casuali possibili@return un array contenente length numeri

casuali compresi fra 0 e n-1*/public static int[] randomIntArray(int length, int n){

int[] a = new int[length];Random generator = new Random();

for (int i = 0; i < a.length; i++)a[i] = generator.nextInt(n);


7


return a;}

/**Stampa tutti gli elementi di un array.@param a l’array a stampare

*/public static void print(int[] a){

for (int i = 0; i < a.length; i++)System.out.print(a[i] + " ");

System.out.println();}

}


8

Capitolo 16 Ordinamento e ricercaFile StopWatch.java/**

Un cronometro accumula il tempo mentre è in azione.Potete avviare e arrestare ripetutamente il cronometro.Potete utilizzare un cronometro per misurare il tempodi esecuzione di un programma.

*/public class StopWatch{

/**Costruisce un cronometro fermo e senza tempo accumulato.

*/public StopWatch(){

reset();}

/**Fa partire il cronometro, iniziando ad accumulare il tempo.

*/


9

Capitolo 16 Ordinamento e ricercapublic void start(){

if (isRunning) return;isRunning = true;startTime = System.currentTimeMillis();

}

/**Ferma il cronometro. Il tempo non viene più accumulatoe viene sommato al tempo trascorso.

*/public void stop(){

if (!isRunning) return;isRunning = false;long endTime = System.currentTimeMillis();elapsedTime = elapsedTime + endTime – startTime;

}

/**Restituisce il tempo totale trascorso.@return il tempo totale trascorso

*/


10

Capitolo 16 Ordinamento e ricercapublic long getElapsedTime(){

if (isRunning){

long endTime = System.currentTimeMillis();elapsedTime = elapsedTime + endTime – startTime;startTime = endTime;

}return elapsedTime;

}

/**Ferma il cronometro e azzera il tempo totale trascorso.

*/

public void reset(){

elapsedTime = 0;isRunning = false;

}

private long elapsedTime;private long startTime;private boolean isRunning;

}


11

Capitolo 16 Ordinamento e ricercaFile SelectionSortTimer.java

import javax.swing.JOptionPane;

/**Questo programma misura il tempo richiestoper ordinare con l’algoritmo di ordinamentoper selezione un array di dimensione specificata dall’utente.

*/public class SelectionSortTimer

{public static void main(String[] args)

{String input = JOptionPane.showInputDialog(

"Enter array size:");int n = Integer.parseInt(input);


12


// costruisce un array casuale

int[] a = ArrayUtil.randomIntArray(n, 100);SelectionSorter sorter = new SelectionSorter(a);

// usa il cronometro per prendere il tempo

StopWatch timer = new StopWatch();

timer.start();sorter.sort(a);timer.stop();

System.out.println("Elapsed time: “+ timer.getElapsedTime() + " milliseconds");

System.exit(0);

}

}


13


Figura 1Tempo impiegato dall’ordinamento per selezione


14


File MergeSorter.java

/**Questa classe ordina un array, usando l’algoritmodi ordinamento per fusione.

*/public class MergeSorter{

/**Costruisce un ordinatore per fusione.@param anArray l’array da ordinare

*/public MergeSorter(int[] anArray){

a = anArray;}

/**Ordina l’array gestito da questo ordinatoreper fusione.

*/


15


public void sort(){

if (a.length <= 1) return;int[] first = new int[a.length / 2];int[] second = new int[a.length – first.length];System.arraycopy(a, 0, first, 0, first.length);System.arraycopy(a, first.length, second,

0, second.length);MergeSorter firstSorter = new MergeSorter(first);MergeSorter secondSorter = new MergeSorter(second);firstSorter.sort();secondSorter.sort();merge(first, second);

}


16


/**Fonde due array ordinati per generare l’array chedeve essere ordinato da questo ordinatore per fusione.@param first il primo array ordinato@param second il secondo array ordinato

*/private void merge(int[] first, int[] second){

// fonde le due metà in un array temporaneo

// il prossimo elemento da considerare nel primo arrayint iFirst = 0;// il prossimo elemento da considerare nel secondo arrayint iSecond = 0;// la prossima posizione libera nell’array aint j = 0;


17


// finché né iFirst né iSecond oltrepassano la fine,// sposta in a l’elemento minorewhile (iFirst < first.length

&& iSecond < second.length){

if (first[iFirst] < second[iSecond]){

a[j] = first[iFirst];iFirst++;

}else{

a[j] = second[iSecond];

iSecond++;}j++;

}


18


// Notate che soltanto una delle due copiature// seguenti viene eseguita

// Copia tutti i valori che rimangono nel primo arraySystem.arraycopy(first, iFirst, a, j,

first.length – iFirst); // Copia tutti i valori che rimangono nel secondo arraySystem.arraycopy(second, iSecond, a, j,

second.length – iSecond);}

private int[] a;}


19


File MergeSortTest.java

/**Questo programma collauda l’algoritmo di ordinamentoper fusione ordinando un array che contiene numeri casuali.

*/public class MergeSortTest{


int[] a = ArrayUtil.randomIntArray(20, 100);ArrayUtil.print(a);MergeSorter sorter = new MergeSorter(a);sorter.sort();ArrayUtil.print(a);

}}


20


Figura 2Tempo di esecuzione dell’orientamento per fusione (rettangoli) confrontato con il tempo di esecuzione dell’ordinamento per selezione (cerchi)


21


Figura 3Il Different Engine di Babbage


22


Figura 4 Suddividere una porzione


23


Figura 5 Estendere le porzioni


24


File LinearSearcher.java

/**Una classe per eseguire ricerche lineari in un

array.*/public class LinearSearcher

{/**

Costruisce l’oggetto di tipo LinearSearcher.@param anArray un array di numeri interi

*/public LinearSearcher(int[] anArray){

a = anArray;}


25

Capitolo 16 Ordinamento e ricerca/**

Trova un valore in un array usando l’algoritmodi ricerca lineare.@param v il valore da cercare@return l’indice in cui si trova il valore, oppure –1

se non è presente nell’array*/public int search(int v){

for (int i = 0; i < a.length; i++){

if (a[i] == v)return i;

}return –1;

}

private int[] a;

}


26

Capitolo 16 Ordinamento e ricercaFile LinearSearchTest.java


/**Questo programma collauda l’algoritmo di ricerca

lineare.*/public class LinearSearchTest{


// costruisci un array casuale

int[] a = ArrayUtil.randomIntArray(20, 100);ArrayUtil.print(a);LinearSearcher searcher = new LineareSearcher(a);

boolean done = false;while (!done)


27


{String input = JOptionPane.showInputDialog(

"Enter number to search for, "+ "Cancel to quit:");

if (input == null)done = true;

else{

int n = Integer.parseInt(input);int pos = searcher.search(n);System.out.println(

"Found in position " + pos);}

}System.exit(0);

}}

28


File BinarySearcher.java

/**Una classe per eseguire ricerche binarie in un array.

*/public class BinarySearcher

{/**

Costruisce un oggetto di tipo BinarySearcher.@param anArray un array ordinato di numeri interi

*/public BinarySearcher(int[] anArray){

a = anArray;}

/**

Trova un valore in un array ordinato, utilizzando l’algoritmo della ricerca binaria.@param v il valore da cercare@return l’indice della posizione in cui si trova

il valore, oppure –1 se non è presente

*/


29


public int search(int v){

int low = 0;int high = a.length – 1;while (low <= high){

int mid = (low + high) / 2;int diff = a[mid] – v;

if (diff == 0) // a[mid] == vreturn mid;

else if (diff < 0) // a[mid] < vlow = mid + 1;

elsehigh = mid – 1;

}return –1;

}

private int[] a;

}


30

Capitolo 16 Ordinamento e ricercaFile PurseTest.java


/**Questa classe collauda la classe Purse chiedendo all’utentedi aggiungere monete ad un borsellino e stampandone ilcontenuto, ordinato in base al valore delle monete.

*/public class PurseTest{


double NICKEL_VALUE = 0.05;

double DIME_VALUE = 0.1;double QUARTER_VALUE = 0.25;

Purse myPurse = new Purse();

boolean done = false;while (!done){


31


String input = JOptionPane.showInputDialog("Enter coin name or Cancel");

if (input == null)done = true;

else{

double value = 0;if (input.equals("nickel"))

value = NICKEL_VALUE; else if (input.equals("dime"))

value = DIME_VALUE; else if (input.equals("quarter"))

value = QUARTER_VALUE;if (value != 0){

Coin c = new Coin(value, input);myPurse.add(c);System.out.println(

"The content of the purse is "+ myPurse);

}}

}System.exit(0);

}}

Capitolo 16 - di.unito.itdamiani/DIDATTICA/aa03/BI-ProgEAlg/Cap16.pdf©Apogeo 2002 Horstmann...

Documents

Transcript of Capitolo 16 - di.unito.itdamiani/DIDATTICA/aa03/BI-ProgEAlg/Cap16.pdf©Apogeo 2002 Horstmann...