Newsgroup: it.scienza.informatica
Titolo: leggenda metropolitana

Vorrei sapere se un mio amico mi ha preso per il c**o o no!
Tale mio amico mi ha detto che un suo ex-compagno di liceo che ora fa
Informatica (o ing. Inform), qualche tempo fa avrebbe messo a punto
un'algoritmo di sorting piu' veloce di Quicksort:
1) E' vero?
2)E' Possibile? (mi sembrava che quick sort fosse il limite teorico)
Rispondete numerosi!!
Andrea
-> it.scienza.informatica (Moderated)
%followup-to
it.scienza.informatica

 2)E' Possibile? (mi sembrava che quick sort fosse il limite teorico)
[dubbio] che sia un altro troll...? [fine-dubbio]
Il limite teorico per l'ordinamento basato su confronti e' O(n log n),
e su questo non penso ci siano dubbi. Il fatto e' che ci sono altri
modi per operare l'ordinamento di dati, sapendo alcune caratteristiche
dei dati stessi: range, possibile ripetizione di dati uguali, ecc...
-- 
 Ciao, Bianco.
 Reply to luca.bianco (at) 
tiscalinet.it


]


 uno n*log(n).
Si', posso essere d'accordo. Il fatto e' che in genere si cerca di
analizzare il problema astraendo dai limiti della macchina: ram, cpu e
cosi' via...
Se non ci sono dettagli precisi sull'implementazione, non si puo' fare
altro che studiare il caso peggiore/migliore/medio.
-- 
 Ciao, Bianco.
 Reply to luca.bianco (at) 
tiscalinet.it


 
Il caso peg/mig/med non raguarda tanto l'implementazione o il hardaware
ma bensì la dipendenza dal algortimo dall'input, non dalla sua dimesione
(che è sempre considerata) ma dalle sue caratteristiche.
In parole povere un conto è ordinare un array già ordinato ed un conto è
ordinarne uno totalmente disordinato (anche se non do dare una
definizione di quest'ultimo termine)
Il quick sort è il migliore algoritmo trovato fino ad oggi per il caso
medio.
Non mi pare però che ci siano teoremi che dimostrino che sia il migliore
in assoluto, sempre nel caso medio.
Quindi secondo me è possibile che se ne trovi uno migliore.
Saluti.


>C'e' anche un'altra cosa da cosiderare: cosa vuol dire "piu' veloce"?
Ma soprattutto: quicksort e` O(nlogn) nel caso medio, non nel caso
pessimo!
Paolo


 2)E' Possibile? (mi sembrava che quick sort fosse il limite teorico)
Basta che tu faccia un'implementazione molto efficace di un radixsort in
base 2...
il problema è che ti devi limitare ai numeri interi!
--
JDS - Wilder
Wild Development Area
------------------------------------------
Radio I'd sit alone and watch your light
My only friend through teenage nights
And ev'rything I had to know
I heard it on my radio
---------------------------------Queen----


> 2)E' Possibile? (mi sembrava che quick sort fosse il limite teorico)
Dunqeu intanto il quick sort non e' il limite teorico..il limite
teorico te l'hanno evidenziato nelle risposte.. quel che e' vero e'
che nella pratica ilk quick-sport si rivela spesso assai veloce piu'
degli altri algoritmi di sort..ma questo puo' dipendere anche dalla
natura dei dati che hai di fronte... in altre parole se il tuo amico
ha realizzato un algoritmo di sort non si puo' dire che "e' piu'
veloce" del qsort... per il semplice fatto che "piu' veloce" in
informatica non vuol dire un piffero... infatti ci si dovrebbe
domandare : "su quale macchina ?" , "con quali dati ?" etc.. percio'
da un tot di decenni si e' optato per la valutazione delle prestazioni
in termini di complessita' e non di "velocita'" 
Augusto Pucci ( 
http://www.prospektiva.it/webmaster/
 )
Webmaster di Prospektiva On-line
http://www.prospektiva.it
Webmaster di 
CO.DI.CI
. Siena
http://codici.supereva.it


Mi pare che nessuno abbia fatto riferimanto al numero di dati da ordinare:
per grandi quantità di dati, n molto grande, n*lon(n) è quello che
implementa il minor numero di operazioni, ma per picole quantità di dati può
essere addirittura  più veloce addirittura un algoritmo che calcola le
combinazioni e trova quella orinata. (n! operazioni?) la funzione verso
l'origine sale in modo diverso che verso l'infinito.


 2)E' Possibile? (mi sembrava che quick sort fosse il limite teorico)
Con il libro di "Algoritmi e Strutture Dati" alla mano, per non dire
fesserie: esiste una dimostrazione che assicura che *ogni* algoritmo
di ordinamento comparativo avra complessita' almeno O(n log n). 
QuickSort ha si' complessita' O(n log n) (cioe' ottima) nel caso 
medio, ma in quello pessimo, che e' il caso di dati gia' ordinati (!), 
la complessita' sale addirittura a O(n^2). Dipende percio' da cosa
ha valuto il tuo amico!
Ciao Ciao
