Newsgroup: it.discussioni.litigi
Titolo: Risultato test per quaquaraqua'.

La domanda era chiaramente tendenziosa, perche' i risultati sono diversi a
seconda del modello computazionale usato. Un sistema ad ipercubo ha
algoritmi piu'
efficenti di un normale sistema basato sul modello della macchina di von
neumann.
Ma non avevo specificato, quindi parliamo di quest'ultimo, senz'altro piu'
diffuso e consolidato.
In un modello di macchina di von neumann, SI DIMOSTRA che un algoritmo di
ordinamento non potra' MAI avere un rendimento asintotico migliore di
n*log(n), con n=numero di oggetti da ordinare (log = logaritmo in base 2)
Questa la teoria, la pratica deve tener conto dell'overhead del codice che
realizza l'ordinamento. Se n e' piccolo, diventa influente, e tanto piu'
l'algoritmo e' complesso, tanto piu' e' inefficente.  Mentre per n grande,
l'overhead diventa ininfluente e conta il comportamento asintotico.
Morale: quicksort per n>n0, ordinamento piu' semplice (bubblesort o persino
ordinamento ingenuo) per n<n0. n0 dipende da mille fattori, ma e' possibile
calcolarne il valore, e l'unione dei due algoritmi rappresenta la scelta
ottima.
Per le strutture multiprocessore (ipercubi ecc..) son riusciti ad arrivare
ad una complessita' O(log n), ma si tratta di soluzioni piuttosto teoriche,
il mondo del multicomputing e' piuttosto immaturo.
E veniamo alle risposte.
Visconte: complessita' logaritmica, quicksort. Non e' logaritmica, ma n*log
n, e come detto dipende dalla quantita' di dati da ordinare. Bocciato.
Charlie: "non esiste". Certo, limite all'ignoranza. Bocciato.
BluDiesel: Per valori piccoli bubblesort, grandi quick o shell. Beh,
promosso.
Alkatraz: "dipende da quello che ci devi fare". Gia', perche' oltre ad
ordinare, cosa ti serve il sort? a pulire il water? "Dipende dalla mole dei
dati", cazzata da programmatore: dipende dalla numerosita', non dalla mole.
Puoi ordinare stringhe 10 grosse un petabyte in pochi cicli di clock.
"dipende dall'architettura del processore": se avessi detto dal numero di
processori ti saresti salvato in corner.  Bocciato con risata.
Sergio: non dipende dalla numerosita' dei dati da ordinare... ti e' andata
davvero male, sorry. Bocciato.

 n*log(n),
Sei proprio sicuro sicuro? Qualsiasi siano i dati da ordinare?
-- 
Per la cronaca ti sto suonando come una zampogna [sirthan]

Sei proprio sicuro sicuro? Qualsiasi siano i dati da ordinare?
se sono ordinati anche n col bubble sort.
---
http://www.gianlucabove.com

 se sono ordinati anche n col bubble sort.
Se sono ordinati cosa cazzo devi ordinare?


Se sono ordinati cosa cazzo devi ordinare?
appunto.
Poi se il dato è uno, sempre n come complessità.
Così insegnano all'università.
Ma alla fine stikazzi.
---
http://www.gianlucabove.com

 La domanda
bzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz.
sbam.

davvero male, sorry. Bocciato.
ROTFL, PdG
Un algoritmo di sorting andrebbe applicato alle idee che ti ruotano
nella capoccia, prima di parlare, PdG
-- 
"Uccidi il tuo personaggio, dammi retta."
		- Sirthan, con nick aavenne

 nella capoccia, prima di parlare, PdG
Te la devo proprio far notare o ci arrivi da solo alla figura di merda che
hai appena fatto?

 Sei proprio sicuro sicuro? Qualsiasi siano i dati da ordinare?
Insisto: cosa ti turba in tutto cio'?



ROTFL, PdG
Vai, fammela notare, PdG

davvero male, sorry. Bocciato.
Ora vieni e puliscimi le scarpe con la lingua.

 Premesso che []
e' solo per il tella power, che sopravvivi a cose cosi'.
vai da mammina e dalle un bacio.
tu non la capisci.
ma nemmeno se te la spiegassi.
--
c.

 e' []
Studia charlie "non esiste", poi ripassa qui che riproviamo.

n*log(n), con n=numero di oggetti da ordinare (log = logaritmo in base 2)
te ne ho appena scritto uno con ordine di complessita' migliore.
Come compito per casa, giustifica il risultato e mettilo d'accordo con
la teoria.