Newsgroup: it.comp.programmare
Titolo: Quicksort: il peggiore algo esistente???

Avete presente i forum sulla programmazione?
Sono capitato in uno di questi forum per *colpa* di google, comunque ho
imparato una cosa strepitosa: il Quicksort è il peggior algoritmo mai
inventato! ;-)
Riporto il testo postato su questo forum (e confermato dai messaggi
successivi).
---
Let me show you a few results:
The performance given by sorting algorithms I implmented
when sorting an array of 2000000 elements :
(executed in a linux system)
RADIX                    0.830s
COUNTING SORT            0.560s
COUNTING SORT(optmized)  0.390s
SHELL                    2.060s
MERGE                    2.180s
QUICKSORT                6.720s
---
Avrei proprio il desiderio di vedere questa versione ottimizzata del
Counting Sort...deve essere molto versatile...
A quanto pare il ShellSort (che è n^1.2) è diventato migliore del MergeSort
(nlogn) e del QuickSort (nlogn), che da oggi in poi chiameremo SlowSort.
Dimenticavo! Su questo forum ho anche letto che il QuickSort è n^2 se
l'array è già ordinato, ma in senso decrescente :-)))
Kiuhnm

 ha scritto nel messaggio
news:48FU9.25827$0v.7...@news1.tin.it...

Be io non sono tanto d'accordo visto che, se non sbaglio, esistono algoritmi
di sort come il bubble sort e altri molto più lenti del quick, e poi il
quick in certi casi ha la stessa velocita computazionale di merge e  heap.
Visto che il caso peggiore (O(n^2)) capita raramente il quick risulta un
algoritmo molto usato.

 ha scritto nel messaggio
news:48FU9.25827$0v.7...@news1.tin.it...

Be io non sono tanto d'accordo visto che, se non sbagli, esistono algoritmi
molto più lenti come il famoso bubble sort e che il quick in casi
particolari risulta dello stesso ordine di grandezza del merge dell'heap e
di altri.

 inventato! ;-)
Se approfondisci un po il discorso, come feci io quando mi serviva un 
sort rapido, noterai che il Quicksort è lento se la lista da ordinare è 
già quasi ordinata.
Per risolvere ci sono 2 modi, almeno:
1) verificare lo stato di "disordine". Se è basso utilizzare ad esempio 
il bubble-sort.
... oppure ...
2) se risulta semplice, "disordinare" volontariamente in modo casuale la 
lista e poi effettuare il Quicksort
Entrambi i metodi incrementano le prestazioni di molto.
-- 
Luc.

 è già quasi ordinata.
Mi dispiace, ma il Quicksort ottiene i tempi migliori con liste già
ordinate. Come fa a essere più lento se la mediana tenderà sempre a essere
l'elemento medio?
Se non mi credi, leggiti "Algoritmi+Strutture Dati = Programmi" visto che
conduce esperimenti su array ordinati, non ordinati e inversamente ordinati.
Comunque possiamo sempre usare il Quicksort lineare...
Dimenticavo: il BubbleSort è pessimo con array ordinati. O si usa il
Bubblesort con segnalatore di scambio oppure si usa lo Shakersort.
Kiuhnm

 ha scritto nel messaggio
news:7yTU9.28127$0v.8...@news1.tin.it...


 Questo nei casi generali...
Esatto, ma quelle che contano sono le costanti. Anche il merge e l'heap sort
sono nlogn, però sono decisamente più lenti.
Esiste anche un Quicksort O(n), però non so quanto sia veloce (a livello di
costanti).
Spero che si sia capito che il mio messaggio iniziale era *completamente*
ironico. I risultati trovati su quel forum sono soltanto indice di scarsa
attitudine alla programmazione...
Kiuhnm


O(n) ???
Saro' io un po' arruginito su ste' cose, ma non esisteva un teorema che
dimostrava che non si può scendere sotto O(nlogn) con gli algoritmi di
ordinamento???
Sono curioso....
Dario

 Sono curioso....
Il teorema dice che nessun metodo di ordinamento basato "esclusivamente" sui
confronti può essere < O(nlogn).
Per esempio il radix sort, che non è basato sui confronti, è O(n).
Sarebbe O(loga(b)*n), dove a è la dimensione della tavola utilizzata per
l'ordinamento e b il valore massimo consentito (per es. 2^32-1).
Se la tavola è lunga 256 elementi e il valore massimo è 2^32 - 1, allora
loga(b) vale esattamente 4 e l'algo è O(4*n).
Qualcuno una volta ha sostenuto che non sia O(n) perchè b non è costante.
'b' è costante per una ragione molto semplice: se gli elementi non avessero
un numero di bit limitato, un confronto non sarebbe O(1), ma O(b) cioè
dipenderebbe dal numero dei bit e in generale gli algoritmi O(n), che per
completezza vanno scritti come O(c1*n + c2) con c1 e c2 costanti,
diventerebbero O(b*n), con b *non* costante.
Comunque il Quicksort O(n) è veramente interessante...se ho tempo posto
qualcosa in proposito.
Kiuhnm