Ciao ragazzi,sono alla fine dell'11esimo capito del librone sul quale studio Java...
Il capitolo 10 era sugli array a livello molto basilare,con sviluppo finale di una classe AddressBook.
Il capitolo 11 tratta degli algoritmi di ricerca ed ordinamento degli array...
dalla ricerca sequenziale alla ricerca binaria e dall'ordinamento sequenza all'heap-sort passando per il bubble-sort..
Uno degli esercizi finali prevedeva lo sviluppo di una classe Heap in grado di ordinare array di interi...
Un esempio di utilizzo della classe
CODICE
Heap oHeap = new Heap
int iArray[] = {1,2,3,4,5,1,2,3,4,5};
int iSorted[];
oHeap.setData(iArray);
iSorted[]=oHeap.sort;
Fatto cio' ci si ritrva con l'array iSorted[] che contiene i valor dell'array iArray[] ordinati.
fino qui non ho avuto molti problemi...
ecco la classe che ho sviluppato...
N.B: Ancora dovrei fare qualche miglioramento,ad esempio utilizzare un unico array sia per la struttura heap sia per inserire i valori ordinati...
Ma quelle sono piccole modifiche che faro' alla fine ^^
CODICE
package pkmyutil.array;
/**
* Questa classe gestisce l'ordinamento di array
* seguento la metodologia di ordinamento Heap-sort
*
* @author -AsCiA-
*
*/
public class Heap {
//----------------------------------------//
//---------------VARIABILI----------------//
//---------------------------------------//
/*
* Implementa la struttura Heap
*/
private int iHeap[];
/*
* Memorizzera la lista finale ordinata
*/
private int iSortedList[];
//----------------------------------------//
//-------------COSTRUTTORE----------------//
//---------------------------------------//
/**
* Un istanza di questa classe permette
* di ordinare un array tramite
* la metodologia di ordinamento
* Heap-Sort.<br>
* Prima di effettuare le operazioni
* di ordinamento bisogna specificare
* l'array da ordinare tramite l'apposito
* metodo setData
*/
public Heap(){
//Costruttore vuoto
}
//----------------------------------------//
//----------------METODI------------------//
//---------------------------------------//
//-----------------//
//-----PUBBLICI----//
//-----------------//
/**
* Questo metodo permette di settare l'array
* sul quale verranno effettuate le operazioni
* di ordinamento.
*
* <br/>
*
* @param iArrayToSort <br>
* Rappresenta l'array da ordinare
*
*/
public void setData(int[] iArrayToSort){
int iLength = iArrayToSort.length;
//Inizializzo i due array
iHeap = new int[iLength];
iSortedList = new int[iLength];
//Copio il valore dell'array passato
for(int i=0; i<iLength; i++){
iHeap[i] = iArrayToSort[i];
}
}
//-------------------------------------------//
/**
* Questo metodo ordina l'array impostato.
*
* <br/>
*
* @return int[]<br/>
* Restituisce un nuovo array ordinato
*/
public int[] sort(){
//Costruisce l'heap
construct();
// for(int i=0;i<iHeap.length; i++){
// System.out.print(iHeap[i] + "-");
// }
//Estrae i valori radice e ricostruisce l'heap ad ogni passaggio
extract();
return iSortedList;
}
//-----------------//
//------PRIVATI----//
//-----------------//
/**
* Questo metodo costruisce la struttura heap
* nell'apposito array
*/
private void construct(){
for(int i=(iHeap.length-2)/2; i>=0; i--){
/*-----------------------------------------------
* Effettuo il passo di ricostruzione
* Nodo di partenza: iHeap.length-2)/2
* Grandezza array: Grandezza della struttura heap
------------------------------------------------*/
rebuild(0, iHeap.length-1);
}
}
//------------------------------------------------------//
/**
* Questo metodo effettua la fase di estrazione e le
* varie ed opportune fasi di ricostruzione dovute
* alla fase di estrzione
*/
public void extract(){
for(int iSize=iHeap.length-1; iSize>=0; iSize--){
//Estraggo il valore dal nodo radice
iSortedList[iSize] = iHeap[0];
//Sposta l'ultimo nodo dell'heap nella radice
iHeap[0] = iHeap[iSize];
/*-----------------------------------------------
* Effettuo il passo di ricostruzione
* Nodo di partenza: Root
* Grandezza array: Grandezza della struttura heap
------------------------------------------------*/
rebuild(0, iSize);
}
}
//------------------------------------------------------//
/**
* Algoritmo di ricostruzione per soddisfare
* il vincolo di relazione fra i valori
*
* @param iNode <br/>
* Rappresenta il nodo esaminato
*
* @param iSize <br/>
* Rappresenta la grandezza dell'array
*
*/
private void rebuild(int iNode,int iSize){
//Nodo corrente sotto esame
int iCurrent;
//Indice del figlio maggiore
int iMaxChildIndex;
//Boolean di controllo per ogni passo
boolean bDone;
iCurrent = iNode;
bDone = false;
//Passo di ricostruzione sul nodo in esame
while(!bDone){
//Controllo che il nodo in esame abbia almeno un figlio
if(2*iCurrent+1 > iSize)
{
//Il nodo non ha figli,il passo di ricostruzione e' terminato
bDone = true;
}
//Il nodo ha almeno un figlio,si procede con il passo di ricostruzione
else
{
//Trovo l'indice del figlio maggiore
iMaxChildIndex=maxChild(iCurrent, iSize);
//Controllo se il figlio maggiore e' maggiore del valore nel nodo corrente
if(iHeap[iMaxChildIndex] > iHeap[iCurrent])
{
//Il figlio e' maggiore del nodo,scambio
swap(iCurrent, iMaxChildIndex);
//Imposto il prossimo controllo sul nodo appena scambiato
iCurrent = iMaxChildIndex;
}
//Il nodo e' maggiore del figlio maggiore,il vincolo di relazione fra i valori per questo nodo e' soddisfatto
else
{
bDone = true;
}
}
}
}
//------------------------------------------------------//
/**
* Restituisce l'indice del figlio maggiore.
*
* @param iCurrentIndex <br/>
* Indice del nodo in esame
*
* @return int <br/>
* Indice del figlio maggiore
*/
private int maxChild(int iCurrentIndex,int iEnd){
int iResult,iRightChild,iLeftChild;
iRightChild = 2*iCurrentIndex+2;
iLeftChild = 2*iCurrentIndex+1;
if(iRightChild <= iEnd && iHeap[iRightChild] > iHeap[iLeftChild])
{
iResult = iRightChild;
}
else
{
iResult = iLeftChild;
}
return iResult;
}
//------------------------------------------------------//
/**
* Questo metodo scambia i valori nell'array
* contenente la strutttura heap
*/
private void swap(int iIndex1,int iIndex2){
int iTemp;
iTemp = iHeap[iIndex1];
iHeap[iIndex1] = iHeap[iIndex2];
iHeap[iIndex2] = iTemp;
}
}
Funziona bene...
Per testarla ecco la classe di test
CODICE
import pkmyutil.array.Heap;
public class MainProve {
public static void main(String[] args) {
Heap heap = new Heap();
int array[] = {90,44,84,77,12,5,38,17,23,90,55,47,47,48,58,65,12,35,32,44,90,40,12,5,5,5,5,55,84};
//Person pArray[] = {}
System.out.println("ARRAY DISORDINATO:");
for(int i=0;i < array.length; i++)
{
System.out.print(array[i] + "-");
}
System.out.println("");
//ORIDNO
heap.setData(array);
int[] arraySort;
arraySort = heap.sort();
System.out.println("");
System.out.println("ARRAY ORDINATO:");
for(int i=0;i < arraySort.length; i++)
{
System.out.print(arraySort[i] + "-");
}
}
}
Ora il problema e' il seguente.
Il prossimo esercizio mi chiede di modificare la classe in modo che ordini non solo interi ma anche oggetti,dicendomi di sostituire int con Object.
Ma oltre questo non ci sono molte altre spiegazioni...
Mi dice di usare per il confronto il metodo compareTo(),ma non capisco se il metodo compareTo() della classe Compare di java.util.Arrays,ed in tal caso devo implementare un interfaccia,o se utilizzare un ipotetico metodo compareTo() dell'oggetto da ordinare...
Ad esempio,qualche capitolo fa,durante lo sviluppo di una classe Person,il libro ha suggerito di implementare un metodo statico piu' o meno cosi
CODICE
public static compareTo(Person p1,Person p2, int I_COSTANT)
{
//Corpo
}
le costanti passate pssono essere ad esempio
I_ORDER_FOR_AGE;
I_ORDER_FOR_NAME;
E restituisce 1 se p1 e' maggiore di p2,-1 se minore,0 se uguali.
Questo metodo sarebbe stato utile per comparare oggetti Person durante procedure di ordinamento,di fatti durante lo sviluppo di AddressBook e' stato molto utile.
Ma adesso la domanda e',se devo sviluppare la classe Heap in modo che ordini oggetti,io non posso essere sicuro che qualsiasi oggetto implementi tale metodo...
Ho dato un occhiata alle soluzioni,giusto per farmi un idea generale sul da farsi,non per copiare ovviamente,e ho notato,che qui il libro in questa soluzione utilizza metodi e classi,che io nemmeno conosco,e lui manco me le ha mai presentate XD
ho notato soprattutto che utilizza una certa classe Comparable,ma non ho idea di come funzioni XD
ho provarto a creare un array di oggetti della mia classe Person ed ordinarla tramite la classe della soluzione,ma al momento dell'esecuzione mi ritrovo un'eccezione che dice:
CODICE
pkmyutil.Person cannot be cast to java.lang.Comparable
Detto cio' ecco la classe heap che dovrebbe ordinare oggetti presentata nelle soluzioni del libro...
CODICE
package pkmyutil.array;
/**
* Basic class for implementing the heapsort algorithm.
* This class works only for any object that implements the compareTo method.
*
* @author Dr. Caffeine
*/
public class Heap {
//----------------------------------
// Data Members
//----------------------------------
/**
* Integer array for implementing a heap
*/
private Object[ ] heap;
/**
* Integer array for the sorted list
*/
private Object[ ] sortedList;
//----------------------------------
// Constructors
//----------------------------------
/**
* Default constructor
*/
public Heap( ) {
}
//-------------------------------------------------
// Public Methods:
//
// void setData ( Object[] )
// Object[] sort ( )
//
//------------------------------------------------
/**
* Sets the interal array to the passed data.
*
* @param data an array to be sorted
*/
public void setData( Object[ ] data ) {
heap = new Object[ data.length ];
sortedList = new Object[ data.length ];
for (int i = 0; i < data.length; i++ ) {
heap[i] = data[i];
}
}
/**
* Sorts the array using heapsort and returns the sorted list.
*
* @return a sorted array of int
*/
public Object[] sort( ) {
construct( ); //construction phase: construct the heap
extract( ); //extraction phase: extract root nodes
return sortedList;
}
//-------------------------------------------------
// Private Methods:
//
// void construct ( )
// void extract ( )
// int maxChild ( int, int )
// void swap ( int, int )
// void testPrint ( int )
//
//------------------------------------------------
/**
* Performs the construction phase of the heapsort.
*/
private void construct( ) {
int current, maxChildIndex;
boolean done;
Comparable item;
for (int i = (heap.length-2) / 2; i >= 0; i--) {
current = i;
done = false;
while ( !done ) {
if ( 2*current+1 > heap.length-1 ) {
//current node has no children, so stop
done = true;
} else {
//current node has at least one child,
//get the index of larger child
maxChildIndex = maxChild( current, heap.length-1 );
item = ( Comparable ) heap[ current ];
if ( item.compareTo(heap[maxChildIndex]) < 0 ) {
swap( current, maxChildIndex );
current = maxChildIndex;
} else { //value relationship constraint
//is satisfied, so stop
done = true;
}
}
}
assert isValidHeap(heap, i, heap.length-1):
"Error: Construction phase is not working " +
"correctly";
}
//testPrint(heap.length); //TEMP
}
/**
* Performs the extraction phase of the heapsort
*/
private void extract( ) {
int current, maxChildIndex;
boolean done;
Comparable item;
for (int size = heap.length-1; size >= 0; size--) {
//remove the root node data
sortedList[size] = heap[ 0 ];
//move the last node to the root
heap[ 0 ] = heap[size];
//rebuild
current = 0;
done = false;
while ( !done ) {
if ( 2*current+1 > size ) {
//current node has no children, so stop
done = true;
} else {
//current node has at least one child, get the index of larger child
maxChildIndex = maxChild( current, size );
item = ( Comparable ) heap[ current ];;
if ( item.compareTo(heap[maxChildIndex]) < 0 ) {
swap( current, maxChildIndex );
current = maxChildIndex;
} else { //value relationship constraint is satisfied, so stop
done = true;
}
}
}
assert isValidHeap(heap, 0, size):
"Error: Extraction phase is not working correctly";
}
}
/**
* Finds the position of the larger child of a node
* at position 'location'.
*
* @param location the position of a node
* @param end the position of the last node in this heap
*
* @return the position of a larger child
*/
private int maxChild( int location, int end ) {
int result, leftChildIndex, rightChildIndex;
Comparable item;
rightChildIndex = 2*location + 2;
leftChildIndex = 2*location + 1;
//Precondition: node at 'location' has at least one child
assert leftChildIndex <= end:
"Error: node at position " + location +
"has no children.";
item = (Comparable) heap[leftChildIndex];
if ( rightChildIndex <= end &&
item.compareTo(heap[rightChildIndex]) < 0 ) {
result = rightChildIndex;
} else {
result = leftChildIndex;
}
return result;
}
/**
* Swaps the values in positions loc1 and loc2
*
* @param loc1 the position of the first int
* @param loc2 the position of the second int
*/
private void swap ( int loc1, int loc2 ) {
Object temp;
temp = heap[loc1];
heap[loc1] = heap[loc2];
heap[loc2] = temp;
}
/**
* Print out the elements for verification purpose
*/
private void testPrint( int limit ) {
for (int i = 0; i < limit; i++) {
System.out.print(" " + heap[i]);
}
System.out.println( " " );
}
/**
* Verifies the valid heap.
*
* @param heap the array containing the heap
* @param start the first (root) position of this heap
* @param end the last position of this heap
*
* @return true if it is a valid heap; otherwise false
*/
private boolean isValidHeap(Object[] heap, int start, int end) {
Comparable max;
for (int i = start; i < end/ 2; i++) {
max = (Comparable) heap[2*i+1];
if (max.compareTo(heap[2*i+2]) < 0)
max = (Comparable) heap[2*i+2];
if (max.compareTo(heap[i]) > 0) {
return false;
}
}
return true;
}
}
Ad una prima occhiata nn mi e' chiarissima...
Cioe' vabbe',il funzionamento generale della classe e' molto chiaro,non riesco a capire in base a cosa vengono comparati gli oggetti prima di essere ordinati...
Devo implementare cosa?
Un interfaccia Comparator<person> o cosa?
Credo che sia un buon libro,ma in questo capitoloo ha corso veramente troppo,in un unico capitolo ha incominciato a parlare da zero,senza nessun accenno precedente di interfacce,interfacce da implementare...
paremetri <t>
Robe di cui non si era mai parlato,tutto buttato li,in un paio di paragrafi,pare che dovessero risparmiare la carta in questo capitolo XD
Spero che qualcuno abbia capito il mio dubbio...
E spero che qualcuno riesca a spiegarmi come fare e soprattuto come funziona esattamente una comparazione di object.
Non ho ancora chiaro esattamenta la storia dell'interfaccia Comparator che va implementata...
Grazie in anticipo
Intanto vedo di ridare un'occhiata a quelle poche righe che spiegano la storia dell'interfaccia Comparator da implementare,magari il problema di fondo e' che non ho capito bene quella...
