Ciao a tutti. Mi sto un po' appassionando a questo metodo di ordimanento. Più efficente del bubble sort e + stabile del quick sort. Ho letto su wikipedia l'algoritmo ma nn l'ho ben compreso.
se io ho questo array
[14 2 9 5 20 1]
il merge sort si occupa (ricorsivamente) di rompere l'array
[14 2 9] | [5 20 1]
Lo rompe ancora una volta
[14] | [2 9] | [5] | [20 1]
e poi...
[14] | [2] | [9] | [5] | [20] | [1]
e a questo punto nn ho capito che caspita fare...
a questo punto entra in atto una procedura chiamata "merge" che fonde le varie sottosequenze (a coppie) tenendo conto dell'ordinamento.Originariamente inviato da FinalFantasy
Ciao a tutti. Mi sto un po' appassionando a questo metodo di ordimanento. Più efficente del bubble sort e + stabile del quick sort. Ho letto su wikipedia l'algoritmo ma nn l'ho ben compreso.
se io ho questo array
[14 2 9 5 20 1]
il merge sort si occupa (ricorsivamente) di rompere l'array
[14 2 9] | [5 20 1]
Lo rompe ancora una volta
[14] | [2 9] | [5] | [20 1]
e poi...
[14] | [2] | [9] | [5] | [20] | [1]
e a questo punto nn ho capito che caspita fare...
Quindi:
[2 14] [5 9] [1 20]
poi
[2 5 9 14] [1 20]
poi
[1 2 5 9 14 20]
Non per niente la procedura merge è la parte + complicata dell'intero merge_sort che altrimenti si ridurrebbe a un pò di chiamate ricorsive.
Invece il quick_sort è un algoritmo che nel caso medio ha un costo che è O(nlog(n)) che teoricamente è + veloce del merge sort andando a guardare le costanti che la notazione O si mangia. Però se nella scelta del pivot si va beccare proprio il mediano risulta che ha un costo di n^2, per questo lo si rende probabilistico (randomizzato) il quick_sort. Il quick sort si usa di + perchè è anche di + facile implementazione.
Ciao ciao
ah ecco...ma questa cosa riduce davvero il tempo rispetto al bubble sort? A me sembra che si mangia una sacco di processore e di memoria...La ricorsione è costosa...Originariamente inviato da conqueror
a questo punto entra in atto una procedura chiamata "merge" che fonde le varie sottosequenze (a coppie) tenendo conto dell'ordinamento.
Quindi:
[2 14] [5 9] [1 20]
poi
[2 5 9 14] [1 20]
poi
[1 2 5 9 14 20]
Non per niente la procedura merge è la parte + complicata dell'intero merge_sort che altrimenti si ridurrebbe a un pò di chiamate ricorsive.
Invece il quick_sort è un algoritmo che nel caso medio ha un costo che è O(nlog(n)) che teoricamente è + veloce del merge sort andando a guardare le costanti che la notazione O si mangia. Però se nella scelta del pivot si va beccare proprio il mediano risulta che ha un costo di n^2, per questo lo si rende probabilistico (randomizzato) il quick_sort. Il quick sort si usa di + perchè è anche di + facile implementazione.
Ciao ciao
Capisco che il bubble sort nel caso peggiore è qualcosa come n! o n^2, però è un for semplice semplice
l'unità di misura di questi algoritmi sono il numero di confronti. Se ci pensi bene il bubble fa O(n^2) confronti perchè va avanti finchè nn scambia + niente. Nel caso del merge il numero di confronti viene ad avere un ordine logaritmico moltiplicato per un fattore n. Intuitivamente n sta perchè la sequenza una volta la deve analizzare tutta, il logn invece (a grandi linee) viene fuori dalla profondità dell'albero della ricorsione che è appunto logaritmica (ogni nodo ha due figli etc..). Il fatto cruciale è che la procedura merge fonde due sequenze già ordinate, e quindi (riprendo dal libro dove ho studiato per l'esame) merge ci mette (l + m -1) confronti a fondere due sequenze già ordinate (dove l e m sono le lunghezze delle sequenze), e l +m -1 è ordine di n.
E' logico che se devi ordinare poche cose ti conviene un algoritmo tipo il selection sort, oppure meglio l'insertion sort, che sono entrambi a ordine di n^2, però meno stupidi del bubble!!
L'unico difettuccio del merge_sort è che la procedura merge ha bisogno di altra memoria ausialiare per fondere. Problema che il quick_sort se implementato in modo opportuno per partizionare in loco non ha.
Ciao ciao
In generale la ricorsione di per se non e' un operazione estremamente lenta dato che allocare variabili locali nello stack e' una procedura che implica semplicemente lo spostamento dello stack pointer. Per quello che ne so il merge sort non viene usato piu' che altro per il fatto che la copia degli array temporanei e' una operazione relativamente lenta e rende l'algoritmo ottimo in teoria ma pessimo in pratica... ma questo non esclude che magari si trovino implementazioni che aggirino questo collo di bottiglia... o magari l'hanno gia' trovato e io non ne so niente... che io sappia in genere l'heap sort sembra essere la soluzione piu' competitiva rispetto allo "strapotere" del quicksort.
my 0.02$
Ciao
Permessi di invio
Rispondi quotando