Pages: [1]   Go Down
Print
Author Topic: QuickSort in O(n lg n)  (Read 1356 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« on: 17-12-2009, 12:50:36 »

è solo una mia riflessione su QuickSort e la sua complessità, per chi ha "tempo da perdere",
che potrebbe anche essere sbagliata (in tal caso vi invito a dirmi che ho detto una cretinata):

QuickSort non è un algoritmo a confronti ottimale perchè il caso peggiore è O(n2). 7

Ma il caso peggiore (mi sbaglio??) si verifica solo quando tutte le partizioni sono del tipo n-1/0;
(se non sbaglio) questo accade solo se:
  • il pivot è il minimo;
  • il pivot è il massimo;

per evitare (e non affidare la scelta del pivot al caso come nel randomizedPartition 7.4) che la scelta del pivot cada in uno dei due casi, si potrebbe banalmente aggiungere un controllo all'inizio della scelta del pivot oppure come per la ricerca delle statitistiche d'ordine con mediane (che esegue una scelta del pivot intelligente), si potrebbe addirittura, (semplificandone l'idea che costa O(nil (n/5))), prendere la mediana di un solo gruppo di 5 elementi(a caso, o i primi, o gli ultimi), con ordinamento in 7 confronti ed estrazione della mediana, tutto in tempo costante teta(1).
Se riuscissmo ad evitare i casi peggiori in questo modo, il caso peggiore a questo punto coinciderebbe col caso medio, QuickSort avrebbe complessità teta(n lg n). Sarebbe quindi un algoritmo ottimale (perchè omega ed O hanno lo stesso limite asintotico 8), proprio come MergeSort ed HeapSort.
Spero che questo ragionamento sul QuickSort non sia sbagliato, me lo ripeto da giorni!
Mi preoccupa il fatto che ci sono arrivato da solo e mi sembra addirittura troppo semplice, logico, banale, lineare...
o magari in fondo sono io che ho semplicemente semplificato qualche parte(il che è più probabile)... Ma cosa?! testate  visto che il libro continua a parlare solo di MergeSort ed HeapSort come algoritmi ottimali di ordinamento a confronti.
help  pray
« Last Edit: 17-12-2009, 15:57:29 by cock86 » Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
salvin
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 259



« Reply #1 on: 17-12-2009, 16:31:45 »

Non l'hai inventato tu, tra gli esercizi c'è anche "partizione sul mediano-fra-tre", si potrebbe anche fare la selezione della mediana in tempo Theta(n), e la complessità di quick-sort resterebbe sempre Theta(nlogn).
Fatto sta che merge-sort è sempre migliore.
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #2 on: 17-12-2009, 17:41:06 »

grazie   non avevo visto l'esercizio, cmq non pretendevo di aver inventato ciò... ma mi chiedevo se questo ragionamento fosse giusto (insomma ho scoperto l'acqua calda)!
comunque il punto fondamentale, era dimostrare che QuickSort è un algoritmo a confronti ottimale con l'applicazione di una piccola e semplice modifica, al contrario di quanto il libro dice nell'introduzione del capitolo 8.
Detto questo se posso permettermi, perchè ritieni MergeSort migliore?entrambi sono ottimali e con stessa complessità teta(n lg n), ma ti ricordo che QuickSort è un algoritmo di ordinamento stabile e su posto a differenza di MergeSort. E se non bastasse, i fattori nascosti (per quel poco che influiscono) sono minori di quasi tutti gli algoritmi di ordinamento a confronto!!!
« Last Edit: 17-12-2009, 17:44:25 by cock86 » Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
salvin
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 259



« Reply #3 on: 17-12-2009, 19:08:00 »

grazie   non avevo visto l'esercizio, cmq non pretendevo di aver inventato ciò... ma mi chiedevo se questo ragionamento fosse giusto (insomma ho scoperto l'acqua calda)!
comunque il punto fondamentale, era dimostrare che QuickSort è un algoritmo a confronti ottimale con l'applicazione di una piccola e semplice modifica, al contrario di quanto il libro dice nell'introduzione del capitolo 8.
Detto questo se posso permettermi, perchè ritieni MergeSort migliore?entrambi sono ottimali e con stessa complessità teta(n lg n), ma ti ricordo che QuickSort è un algoritmo di ordinamento stabile e su posto a differenza di MergeSort. E se non bastasse, i fattori nascosti (per quel poco che influiscono) sono minori di quasi tutti gli algoritmi di ordinamento a confronto!!!

No, puoi fare la fusione "in place" quindi anche il MergeSort, e se devi fare la selezione della mediana il QuickSort viene leggermente più lento anche se la complessità resta Theta(nlogn)
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #4 on: 18-12-2009, 09:05:23 »

mmm si  ok se cerchi la mediana dell'intero array, ma non è necessario. Basta la mediana di 5 qualsiasi numeri, e 7 confronti(fattore pressochè nullo) per avere un pivot che ti garantisca nel caso peggiore il  caso medio. 
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: