Il problema dell’ordinamento di un array in Java si può risolvere in molti modi, in questo articolo vediamo un procedimento efficiente (complessità media O(n log n)) indipendente dal contenuto dell’array.

Questa classe contiene al suo interno anche un array di etichette (quando si ordinano dei dati è comodo avere un riferimento testuale) del tutto opzionale. Il procedimento si può ri-utilizzare anche in altri linguaggi purché si adotti, se esiste, il costrutto equivalente al Generic Java del linguaggio di codifica (es. i template del C++).

import java.util.Comparator;
  public class QuickSort<generica><generica>&gt;  {
    String [] label;
    Generica[] array;
    private  void  swap( int i, int j) {
    Generica  tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
    String sTmp =label[i];
    label[i] = label[j];
    label[j] = sTmp;
  }
 
  private int partition(int low, int high) {
    int index = low+(int)(Math.round(Math.random()*(high - low)));
    Generica pivot = array[index];
    swap( index, high);
    for (int i = index = low; i &lt; high; ++ i) {
      if (array[i].compareTo(pivot) &lt;= 0) {
        swap( index++, i);
      }
    }
    swap( index, high);
    return (index);
  }
 
  private  void quickSort(int  low, int high) {
    if (high &gt; low) {
      int index = partition( low, high);
      quickSort( low, index - 1);
      quickSort( index + 1,  high);
    }
  }
 
  public  void quickSort(Generica [] array) {
    this.array=array;
    quickSort( 0, array.length - 1);
  }
 
  public  void quickSort(Generica [] array, String label[]) {
    this.label=label;
    this.array=array;
    quickSort( 0, array.length - 1);
  }
}</generica></generica>

Segnala presso:

(Nessun voto)

 Loading ...

9 Responses to “Ordinare un array in Java utilizzando generic e QuickSort”

1. rvinside Says:
   February 12th, 2008 at 2:02 pm

   Grazie per la dritta, mi è molto utile la mia domanda (forse sciocca) è questa: lo stesso metodo è utilizzabile nello stesso identico modo anche per gli arraylist?

2. alessandro.simonetta Says:
   February 12th, 2008 at 4:46 pm

   Le domande dei programmando-nauti non sono mai sciocche! Un ArrayList è oggetto istanza di una
   classe con delle caratteristiche di gestione (dinamica), quel metodo gestisce il tipo primitivo array quindi è molto + veloce (la gestione di un array “tipo primitivo” è statica:una volta allocato non si può ridimensionare a meno di riassegnarlo in un altro spazio di memoria più grande/piccolo).

3. rvinside Says:
   February 13th, 2008 at 12:07 pm

   “la gestione di un array “tipo primitivo” è statica:”
   infatti era per questo che chiedevo!

4. alessandro.simonetta Says:
   February 13th, 2008 at 2:03 pm

   Chiedo scusa ma non avevo capito la domanda perché se si utilizzano le collezioni di dati, di solito, esse hanno già dei metodi di sort precostituiti. Il problema è che poi la loro gestione richiede un maggior overhead da parte dell’interprete. In ogni caso la risposta alla tua domanda è affermativa.

5. Giordano Says:
   February 15th, 2008 at 11:14 pm

   essendo un newbie di java…
   …puoi trascrivere un esempio completo ove sia presente anche il metodo main..
   Grasssie

   P.S: ma quelle scritte “” e “>” fanno parte anch’esse del codice java o sono una formattazione aggiunta dal cms ?

6. Giordano Says:
   February 15th, 2008 at 11:16 pm

   le scritte (visto che non si leggono) sarebbero generica_incluso_tra_freccette e poi anche e_commerciale,punto_e_virgola,g,t

7. alessandro.simonetta Says:
   February 18th, 2008 at 1:04 am

   scusa ma il mio plug-in da i numeri, ti allego il file corretto senza evidenza della sintassi, e un file main di prova:
   import java.util.Comparator;
   public class QuickSort<Generica extends Comparable> {
   String [] label;
   Generica[] array;
   private void swap( int i, int j) {
   Generica tmp = array[i];
   array[i] = array[j];
   array[j] = tmp;
   String sTmp =label[i];
   label[i] = label[j];
   label[j] = sTmp;
   }
   private int partition(int low, int high) {
   int index = low+(int)(Math.round(Math.random()*(high - low)));
   Generica pivot = array[index];
   swap( index, high);
   for (int i = index = low; i < high; ++ i) {
   if (array[i].compareTo(pivot) low) {
   int index = partition( low, high);
   quickSort( low, index - 1);
   quickSort( index + 1, high);
   }
   }
   public void quickSort(Generica [] array) {
   this.array=array;
   quickSort( 0, array.length - 1);
   }
   public void quickSort(Generica [] array, String label[]) {
   this.label=label;
   this.array=array;
   quickSort( 0, array.length - 1);
   }
   }

   Un possibile main di esempio:
   ——————————————–
   public class ProvaQuickSort {
   public static void stampaVettore(Double [] altezza, String [] nome) {
   for (int i=0; i<altezza.length;i++)
   System.out.println(nome[i]+” “+altezza[i]);
   }
   public static void main (String [] args){
   QuickSort qs= new QuickSort();
   Double altezza[]={ new Double(1.73),new Double(1.67),new Double(1.52)};
   String[] nome={”Mario Rossi”, “Giuseppe Verdi”, “Paolo Bianchi”};

   System.out.println(”prima dell’ordinamento”);
   stampaVettore(altezza,nome);
   qs.quickSort(altezza,nome);
   System.out.println(”dopo ordinamento”);
   stampaVettore(altezza,nome);
   }
   }

8. alessandro.simonetta Says:
   February 18th, 2008 at 1:08 am

   poiché le parentesi angolari fanno impazzire anche il povero wordPress, nella prima riga devi aggiungere dopo Comparator la classe Generica tra parentesi angolari (quindi la prima riga un attimo prima della
   graffa ha due parentesi angolari chiuse (insomma come uno shift del C++ per comprenderci ;))
   Se troviamo ancora problemi allego il file in un altro articolo…

9. alessandro.simonetta Says:
   February 18th, 2008 at 10:00 am

   …stesso discorso per le if, bisogna recuperare gli operatori di maggiore e minore nel listato di sopra

Inserisci il tuo Commento: