MERGE SORT
ALGORITMO:
procedure merge (var A: vettore; p,q,r: integer);
var i,j,k,h: integer;
B: vettore;
begin
i:=p;
j:=p;
k:=q+1;
while (i<=q) and (k<=r) do begin
if A[i]<=A[k] then begin
B[j]:=A[i];
i:=i+1;
end
else begin
B[j]:=A[k];
k:=k+1;
end;
j:=j+1;
end;
if k>r then
for h:=i to q do begin
B[j]:=A[h];
j:=j+1;
end
else
for h:=k to r do begin
B[j]:=A[h];
j:=j+1;
end;
for h:=p to r do
A[h]:=B[h];
end;
procedure merge sort(var A:vettore; p,r:integer);
var q: integer;
begin
if (p<r) then begin
q:=(p+r) div 2;
merge sort(A,p,q);
merge sort(A,q+1,r);
merge (A,p,q,r);
end;
end;
var i,j,k,h: integer;
B: vettore;
begin
i:=p;
j:=p;
k:=q+1;
while (i<=q) and (k<=r) do begin
if A[i]<=A[k] then begin
B[j]:=A[i];
i:=i+1;
end
else begin
B[j]:=A[k];
k:=k+1;
end;
j:=j+1;
end;
if k>r then
for h:=i to q do begin
B[j]:=A[h];
j:=j+1;
end
else
for h:=k to r do begin
B[j]:=A[h];
j:=j+1;
end;
for h:=p to r do
A[h]:=B[h];
end;
procedure merge sort(var A:vettore; p,r:integer);
var q: integer;
begin
if (p<r) then begin
q:=(p+r) div 2;
merge sort(A,p,q);
merge sort(A,q+1,r);
merge (A,p,q,r);
end;
end;
SPIEGAZIONE ALGORTIMO
Concettualmente, il merge sort lavora in questo modo:
1. Divide la lista non ordinata in due sottoliste di circa metà dimensione
2. Ordina ciascuna delle due sottoliste
3. “Fonde” (merge in inglese) le due liste ordinate in un’unica lista ordinata
COMPLESSITA’
Il Merge Sort nel caso migliore e in quello pessimo ha complessità O(n log n) .
Nel caso pessimo, il merge sort effettua il 30% di comparazioni in meno rispetto a quelli che il quicksort effettua nel caso migliore; questo perché il merge sort molto spesso necessita di meno confronti.
In termini di mosse, la complessità del merge sort nel caso pessimo è O(n log n), la stessa complessità del quicksort nel caso migliore, e il miglior caso del merge sort prende circa la metà del tempo del caso pessimo.
Per capire perché si arriva a O(n log n) bisogna considerare che in un vettore di taglia n, le suddivisioni fino a giungere a vettori di taglia 1 sono log n, mentre la procedura di merge (fusione dei due semivettori) richiede n confronti, quindi si ha che il numero totale di operazioni è pari a n log n.
Il merge sort effettua 2n-1 chiamate ricorsive al metodo nel caso pessimo, in confronto agli n del quicksort.
E’ comunque molto più efficiente del quicksort, in quanto il quicksort "vorrebbe" suddividere a ogni passo il vettore in due sotto-vettori "circa uguali", delimitati da un elemento "limite" (pivot), ma mentre il merge sort si assicura questa proprietà (spezzando il vettore a metà), il quicksort ci spera soltanto, infatti ottiene lo scopo se il pivot è "ben scelto", ma negli altri casi, funzionerà "peggio".
Queste considerazioni ci inducono a pensare che il quicksort riesca al più a emulare il merge sort, quando ha fortuna, ma senza riuscire a eguagliarlo in tutti i casi.
Torna a Programmazione e Lab.
Non ci sono commenti in questa pagina. [Scrivi commento]