Newsgroup: it.comp.java
Titolo: Quick Sort e Hashtable, Aiuto!

Ciao a tutti,
premetto che sto imparando java e non sono molto ferrato ancora sul
linguaggio.
Avrei il seguente problema: ho un algoritmo di ordinazione QuickSort (che
riporto qui sotto) che funziona passandogli un array di elementi e lui li
ordina.
Io dovrei modificarlo per farlo diventare un po piu generale usando ad
esempio una hashtable invece dell'array, ma non ho idea di dove metter mano!
Se avete aiuti o suggerimenti sarň ben felice di ascoltarli!
Ecco il codice iniziale:
static item [] QuickSort (item [] a, int l, int r) {
  if (l < r) {
    display(a,l,r);
    int i = l;
    int j = r;
    int k = (int) ((l+r) / 2);
    item pivot = a[k];
    do {
      while (a[i].less(pivot)) i++;
      while (pivot.less(a[j])) j--;
      if (i <= j) {
        item t = (item) a[i].clone();
        a[i] = a[j];
        a[j] = t;
        i++; j--;
      }
    } while (i < j);
    a = QuickSort (a, l, j);
    a = QuickSort (a, l, r);
  }
  return a;
}
Grazie a tutti,
Ciao Ale.

Se avete aiuti o suggerimenti sarň ben felice di ascoltarli!
Mi sa tanto di progettino universitario, se cosě non fosse prometto di aiutarti, altrimenti... :/

 ha scritto nel messaggio
news:40f86tkmdpb626s2e...@4ax.com...

Ok lo ammetto č un compitino dell'uni ma sono due notti che non ci dormo
sopra! per favore anche solo un consiglio non chiedo il metodo bello che
pronto!
thx.

 writes:
A> Ok lo ammetto č un compitino dell'uni ma sono due notti che non ci dormo
A> sopra! per favore anche solo un consiglio non chiedo il metodo bello che
A> pronto!
Ma guarda 'sti impuniti. 
Una dritta  di una sola  parola. Comparable. E  ora vai, ti  prendi la
documentazione e  te la studi  e ti prendi  un rimbrotto per  non aver
pensato  prima ad  usare  le interfaccie.  Ma  il corso  lo segni  per
mettere un voto sul libretto o per imparare quel poco che insegnano ?
\begin{echelon}
colonel AK-47 jihad PLO Nazi Honduras BATF Treasury Delta Force NSA
Peking cryptographic plutonium SDI [Hello to all my fans in domestic
surveillance]
\end{echelon}
--
Gian Uberto| main(){printf(&unix["\021%six\012\0"],(unix)["have"]+"fun"-0x60);}
Lauri      |                        David Korn, 1987 ioccc best one liner 
(aka saint)|-------------------------------------------------------------------
em@ail: sierra alfa india november tango AT echo november golf DOT india tango

pronto!
E certo: l'ho capito dall'inutilità della cosa, nel JDK c'è già tutto fatto
con un metodo statico sort che ordina tutto, utilizzando il QuickSort.
Comunque, questo è il QuickSort, parti da qui...
/*
 QuickSort.java - Una semplice implementazione del QuickSort
 Java Code by Castagna
 
*/
import java.lang.*;
import java.util.Random;
class QuickSort {
  private static void swap (int[] array, int a, int b) {
    int object = array[a];
    array[a] = array[b];
    array[b] = object;
  } // swap
 
  public static void quicksort(int[] array, int i, int j) {
    if (i < j) {
      swap(array, i, (i + j) / 2);
      int a = i;
      for (int b = i + 1; b <= j; b++) {
        if (array[b] < array[i])
          swap(array, ++a, b);
        }
      swap(array, i, a);
      quicksort(array, i, a - 1);
      quicksort(array, a + 1, j);
    }
  } // quicksort
 
  public static void quicksort(int[] array) {
    quicksort(array, 0, array.length - 1);
  } // quicksort
} // QuickSort
public class DemoQuickSort {
  public static  void main(String args[]) {
    int MAX_NUM = 10000;
    int a[] = new int[MAX_NUM];
    // Inizializza l'array di interi a[] con numeri casuali
    Random r = new Random();
    for (int i = 0; i < MAX_NUM; i++)
      a[i] = r.nextInt(10000);
 
    // Scrive a video l'array prima dell'ordinamento
    for (int i = 0; i < a.length; i++)
      System.out.print (a[i] + " ");
    System.out.println ("");
    // Per cronometrare il tempo impiegato...
    long inizio = System.currentTimeMillis();
 
    QuickSort.quicksort (a); // Ordina l'array di interi a[] con l'algoritmo QuickSort
 
    // Calcola il tempo impiegato e lo scrive a video in sec.
    long time = (System.currentTimeMillis() - inizio);
    // Scrive a video l'array dopo l'ordinamento
    for (int i = 0; i < a.length; i++)
      System.out.print (a[i] + " ");
    System.out.println ("");
 
    // Scrive il tempo impiegato per l'ordinamento
    System.out.println("Tempo impiegato, circa " + time + " millisecondi. ");
  } // main
 
} // DemoQuickSort
... io lo generalizzerei utilizzando dei Vector invece che array ;)
Attenzione che probabilmente dovrai studiarti anche l'interfaccia
java.lang.Comparable
Bye

 Mi sa tanto di progettino universitario
Ho la sensazione che in questo ng passino molti compitini universitari..
:-)

Ho la sensazione che in questo ng passino molti compitini universitari..
Già, io li riconosco per il grado di inutilità e per lo scarso 
utilizzo degli oggetti già presenti nel JDK ;)
Hai professoroni se una cosa non è sufficientemente complessa
non piace; mi verrebbe da dire KISS = Keep It Simple and Stupid,
oppure a seconda delle versione, e questa megli si addice nel
caso accademico, Keep It Simple, Stupid!
Senza rancore! ;)
Bye

Comunque, questo è il QuickSort, parti da qui...
Ti dirò di più, se non hai voglia di scrivere codice, copialo 
direttamente dai sorgenti della Sun, il tuo professore non se
ne accorgerà (non saprà nemmeno che sono disponibili).
Se non hai i sorgenti usa un decompilatore:
http://jode.sourceforge.net
 ;)
Ricorda che il software non è brevettabile in Europa, per fortuna!!!
Il QuickSort è un algoritmo libero e standard!!!!
Bye

> Mi sa tanto di progettino universitario
PC> Ho la sensazione che in questo ng passino molti compitini universitari..
PC> :-)
Beh, java è  un ottimo linguaggio per insegnare  a programmare in modo
object oriented. E se insegni  la programmazione OO allora ti troverai
programmatori in grado di fare buoni programmi anche quando utilizzano
linguaggi procedurali vecchio stile...
\begin{echelon}
smuggle kibo Ft. Bragg Serbian AK-47 explosion quiche Legion of Doom
Noriega Nazi World Trade Center radar Soviet assassination Ortega


 writes:
C> ... io lo generalizzerei utilizzando dei Vector invece che array ;)
C> Attenzione che probabilmente dovrai studiarti anche l'interfaccia
C> java.lang.Comparable
La seconda più  che la prima direi... Non  ho controllato il quicksort
che aveva pubblicato lo studente,  ma a naso l'esercizio era orientato
a   fare  una   quicksort  che   ordinasse  un   vettore   di  oggetti
ordinabili... (bisognerebbe vedere il testo dell'esercizio - da me "la
comprensione del  testo dell'esercizio fa(ceva)  parte del superamento
della prova")
\begin{echelon}
security cracking Saddam Hussein SDI genetic Ft. Meade munitions
Peking North Korea Ortega Serbian FSF Khaddafi Marxist South Africa



cocncordo anchio sono studente di informatica e spesso i progettini sono
inutili e faticosi 
d'altraparte questo e newsa su java anche per imparare java se questo
serve a rimediare
o integrare corsi un po' superficiali e sbrigativi ben venga non
credete?
-- 
/////////////////////////////////////////////////////////////////////
/
/	 
cyber...@libero.it
   # ICQ N° 70608137                           
/     	   D.A.V.I.D. is A Vision of Inner Demons
/	
/	Redattore di Luci ad Ovest e membro della Harlequin crew
/	Visita Luci ad Ovest! (
http://www.gilda.it/luciadovest
)
/	Presente nella computazione del progetto  S.E.T.I@Home
/	   (
http://setiathome.ssl.berkeley.edu/
)
/////////////////////////////////////////////////////////////////////


ed ecco a voi un altro futuro promettente programmatore che non sara` in
grado di scriversi neanche un quicksort... complimenti: bel
suggerimento!
-- 
Ciao,    |  I can see tomorrow   I can see the world to come
 Matteo  |  I can see tomorrow   Hear the pandemonium 
         |                     -- Killing Joke (Pandemonium)

 suggerimento!
Io sono 10 anni che programmo con linguaggi diversi e non credo che sia tu
il tizio che mi viene a dire che non so scrivere un quick sort! Infatti se
ti leggi il mio primo post il quick sort ce lo trovi gia fatto! ma scusate
se ho chiesto un'implementazione con un hashtable è perchè non riesco a
concepirla e vorrei capire come cavolo si fa! e soprattutto vorrei imparare
java. Non è colpa mia se il mio prof spiega da cane, io la mia buona volontà
ce l'ho sempre messa. Se non me ne fregasse niente la mattina starei a letto
a dormire invece di sbattermi all'uni!
GRAZIE.

 Io sono 10 anni che programmo con linguaggi diversi [...]!
vedi sopra.


Tu sei nato che sapevi tutto? Complimenti, io no.
Ehy... dai non prendertela ;)
Alle volte si generalizza... siamo qui tutti per imparare gli uni dagli altri!
Buona giornata!

questo ti sei sentito offeso me ne scuso.
Beh, anch'io mi sono espresso male, con il mio consiglio volevo
invitarlo a vedere l'implementazione che la Sun da di QuickSort,
perché fa proprio quello che gli serve!!!!!
Imparare dagli esempi e dai sorgenti credo sia il modo migliore:
sempre e comunque. Inoltre si risparmia tempo...
Un buon programmatore non è chi sa fare tutto a memoria ma chi
sa capire e ricorda dove trovare ciò che gli serve.
Bye ;)

 writes:
A> ma scusate
A> se ho chiesto un'implementazione con un hashtable è perchè non riesco a
A> concepirla e vorrei capire come cavolo si fa!
Prima di tutto  le mie scuse per aver frainteso il  tuo post. Ti avevo
indicato  l'interfaccia Comparable  perché pensavo  che  la generalità
fosse sul tipo degli input.
Sinceramente mi lascia perplesso l'uso della classe Hashtable. 
In  una  tabella di  hash  la posizione  di  un  elemento dipende  dal
contenuto della  chiave dell'elemento stesso (che al  più coincide con
l'intero elemento) in quanto viene calcolata applicando una funzione f
alla chiave:
		p = f(chiave)
Spostare un elemento vuol dire "perderlo" in quanto si rompe il legame
chiave-posizione.
Tra l'altro l'ordinamento ha poco senso anche perché una hash table ha
la  caratteristica  di  rendere   il  tempo  di  accesso  (quasi  [*])
indipendente  dal   valore  e  assimilabile  al   tempo  di  calcolare
f(chiave). Invece l'accesso ad un dato in una tabella ordinata o in un
albero binario  ha un tempo  massimo logaritmico (logaritmo in  base 2
del  numero  degli  elementi  contenuti) ma  alcuni  elementi  vengono
ricuperati più velocemente di altri.
[*] In realtà in  una hash table si deve gestire anche  il caso in cui
    f(chiave1) = f(chiave2) con chiave1 != chiave2, quindi il tempo di
    accesso ad un elemento può aumentare.
Al posto della Hashtable ti  consiglierei anche io il Vector, un array
a dimensione dinamica (leggersi sulla documentazione i metodi).
Prima riscriverei Quicksort utilizzando un Vector al posto dell'array,
poi  verificherei  se  si  hanno  vantaggi (di  tempo)  procedendo  in
quest'altro modo:
	Si estrae l'array dal vector
	Si ordina il vector
	Si rigenera il vector dall'array
Se hai dubbi, fai un fischio. L'e-mail è in fondo alla mia signature,
non immediato da leggere ma....


 a dormire invece di sbattermi all'uni!
Internet mi piace anche per questo.. :-)

perchč non riesco a concepirla e vorrei capire come cavolo si fa! 
Cosa, esattamente, non concepisci?
Un'hash table e' una mappa tra chiavi (univoche) ed entries. Cio' significa che 
puoi inserirci coppie (chiave, entry) e, data una chiave, puoi recuperare una 
entry.
Le due operazioni fondamentali sono quindi 
    	put(chiave, entry) 
    	get(chiave)
Si chiama "hash table" perche' il posizionamento effettivo della entry nella 
memoria e' determinato da un "rimescolamento" (hashing) basato sulla chiave, il 
quale ha certe desiderabili proprieta' statistiche, tali che chiavi diverse 
tendono a generare posizioni diverse. Formalmente, hai una funzione 
hash(chiave) che genera, ad esempio, un indice in un array; e quindi le due 
operazioni sono implementate come
     	put(chiave, entry) : array[ hash(chiave) ] = entry
    	get(chiave) : return array[ hash(chiave)]
il che risulta in una notevole velocita' di accesso se comparata ad
altre strutture dati; ad esempio, con una lista unidirezionale, per 
implementare get(chiave) devi scorrere la lista dall'inizio finche' non 
incontri la chiave o la lista e' finita.
Se per caso due chiavi diverse generano lo stesso indice, si ha una 
"collisione": bisogna mettere due elementi nella stessa posizione dell'array.
Siccome questo non e' possibile, il trucco e' di mettere nell'array una *lista* 
(o altra struttura dati) di entries, invece di metterci direttamente le 
entries. Inserendo un elemento, in caso di collisione, se nella posizione hash
(chiave) c'e' gia' una entry, si fa semplicemente l'append sulla lista.
Formalmente,
    	put(chiave, entry):
    	    	if (array[ hash(chiave) ] is null) {
    	    	    	array[ hash(chiave) ] = new Lista()
    	    	}
    	    	array[ hash(chiave) ].append(chiave+entry)
    	get(chiave):
    	    	Lista lista = array[ hash(chiave) ]
    	    	return lista.cercaEntryInLista(chiave);
 
dove "cercaEntryInLista" e' una funzione di ricerca sulla lista che localizza 
l'entry con una certa chiave.
Ora, in Java, nell'implementazione "java.util.Hashtable", sia chiavi che 
entries sono oggetti. Le classi degli oggetti usati come chiave, in 
particolare, devono fare l'override dei metodi equals() e hashCode() di 
java.lang.Object in modo sensato. Le classi standard hanno gia' tale override, 
quindi sono usabili direttamente.
Ad esempio, quindi, puoi scrivere
 Hashtable table = new Hashtable();
 table.put("pinco","pallino");
 System.out.println( table.get("pinco") );
usando oggetti di classe java.lang.String. L'unica nota e' che il tipo 
dell'oggetto ritornato da get() e' java.lang.Object quindi devi di norma fare 
un cast per convirtirlo alla classe effettiva della entry.
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun

Grazie dell'aiuto a tutti e scusate lo scatto di nervosismo ma sto veramente
facendo le corse per finire i programmi.
Ale  : )