View Single Post
Old 06-09-2005, 10:57   #4
pinok
Senior Member
 
Iscritto dal: Jun 2001
Città: Alessandria (provincia)
Messaggi: 4772
Gli esempi standard del quick sort ordinano oggetti numerici.
Devi modificarlo in modo che i controlli siano fatti esternamente in base ai criteri che vuoi tu.

Faccio prima a riportarti il codice. Ti serve una classe astratta che và bene per tutti gli ordinamenti

Codice:
import java.util.*;

public abstract class Ordina
{	
  /** 
   * 	Algoritmo di quickSorting, da inizializzare con il vettore da 
   *	ordinare e gli indici estremi del vettore 
   * 	(solitamente left = 0 e right = element.size()-1) 
   **/
  public void qs (Vector element, int left, int right) 
  {
    int i,j;
    Object x, y;
        
    i = left;
    j = right;
    x = element.elementAt((left+right)/2);
        
   do
   {
     while (minimum (element.elementAt(i), x) && i<right) i++;
     while (minimum (x, element.elementAt(j)) && j>left) j--;
            
     if (i<=j)
    {
       y = element.elementAt(i);
       element.setElementAt (element.elementAt(j), i);
       element.setElementAt (y, j);
       i++;
       j--;
      }
    } while (i<=j);
        
    if (left<j) qs (element, left, j);
    if (i<right) qs(element, i, right);
  }
	
  /**
   * Interfaccia da implementare di volta in volta
   *
   * @param obj1 Primo oggetto da confrontare
   * @param obj2 Secondo oggetto da confrontare
   */
  protected abstract boolean minimum(Object obj1, Object obj2);
}
Poi ti devi fare una classe che estende quella astratta ridefinendo il metodo minimum secondo le tue esigenze. Ad es, se i tuoi oggetti sono istanze di Studente con l'anagrafica di ognuno, per ordinare in base al cognome e nome (messi in uppercase per evitare differenze di ordinamento in base alle maiuscole):

Codice:
public class OrdinaStudenti extends Ordina
{	
   /**
    * Interfaccia da implementare di volta in volta
    *
    * @param obj1 Primo oggetto da confrontare 
    * @param obj2 Secondo oggetto da confrontare
    */
   protected boolean minimum(Object obj1, Object obj2)
   {
      String nome1 = ((Studente)obj1).getCognome().toUpperCase()+" "+((Studente)obj1).getNome().toUpperCase();
      String nome2 = ((Studente)obj2).getCognome().toUpperCase()+" "+((Studente)obj2).getNome().toUpperCase();
		
      if( nome1.compareTo(nome2)<0) return true;
      
      return false;
   }
}
Se hai da fare controlli più complicati, basta che li scrivi dentro al metodo minimum.
Se hai oggetti diversi da controllare, basta che crei nuove classi simili ad OrdinaStudenti perché qs và sempre bene per come è stato scritto (astratto).

Per richiamare l'ordinamento del vettore lista, devi solo scrivere:

Codice:
if (lista.size()>1) 
{
  OrdinaStudenti ordina = new OrdinaStudenti();
  ordina.qs(lista, 0, lista.size()-1);
}
Ricordati di mettere l'if (lista.size()>1) perché ti evita errori nel caso non ci fossero almeno 2 elementi (d'altra parte, che senso ha ordinare uno o zero elementi ??)
pinok è offline   Rispondi citando il messaggio o parte di esso