La versione più recente è stata modificata il 2007-02-17 12:11:54 da ViViana
Aggiunzioni:
for h:=p to r do
A[h]:=B[h];
Omissioni:
for h:=p to r do
k:=q+1;
if A[i]<=A[k] then begin
for h:=i to q do begin
merge sort(A,p,q);
merge sort(A,q+1,r);
merge (A,p,q,r);
end;
Omissioni:
i:=p;
j:=p;
k:=q+1;
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;
for h:=i to q do begin
B[j]:=A[h];
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];
q:=(p+r) div 2;
merge sort(A,p,q);
merge sort(A,q+1,r);
merge (A,p,q,r);
Modificato il 2006-03-02 21:09:10 da ViViana
Aggiunzioni:
Modificato il 2006-03-02 21:05:48 da ViViana
Aggiunzioni:
Il Merge Sort nel caso migliore e in quello pessimo ha complessità O(n log n) .
Omissioni:
Il Merge Sort nel caso migliore e in quello pessimo ha complessità .
Modificato il 2006-03-02 21:05:12 da ViViana
Aggiunzioni:
Il Merge Sort nel caso migliore e in quello pessimo ha complessità .
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.
La versione più vecchia di questa pagina è stata modificata il 2006-03-02 21:04:26 da ViViana []
ALGORITMO:
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’
Torna a Programmazione e Lab.
Aggiunzioni:
for h:=p to r do
A[h]:=B[h];
Omissioni:
for h:=p to r do
A[h]:=B[h];
Modificato il 2006-03-06 23:34:23 da ViViana
Aggiunzioni:
%%(pascal)
Modificato il 2006-03-02 21:11:14 da ViViana
Aggiunzioni:
i:=p;
j:=p; Modificato il 2006-03-06 23:34:23 da ViViana
Aggiunzioni:
%%(pascal)
Modificato il 2006-03-02 21:11:14 da ViViana
Aggiunzioni:
i:=p;
k:=q+1;
if A[i]<=A[k] then begin
B[j]:=A[i];
i:=i+1;
end
else begin i:=i+1;
end
B[j]:=A[k];
k:=k+1;
end;
j:=j+1;k:=k+1;
end;
for h:=i to q do begin
B[j]:=A[h];
j:=j+1;
end
for h:=k to r do beginj:=j+1;
end
B[j]:=A[h];
j:=j+1;
end;
for h:=p to r do j:=j+1;
end;
A[h]:=B[h];
q:=(p+r) div 2; merge sort(A,p,q);
merge sort(A,q+1,r);
merge (A,p,q,r);
end;
Omissioni:
i:=p;
j:=p;
k:=q+1;
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;
for h:=i to q do begin
B[j]:=A[h];
j:=j+1;
end 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];
q:=(p+r) div 2;
merge sort(A,p,q);
merge sort(A,q+1,r);
merge (A,p,q,r);
Modificato il 2006-03-02 21:09:10 da ViViana
Aggiunzioni:
Modificato il 2006-03-02 21:05:48 da ViViana
Aggiunzioni:
Il Merge Sort nel caso migliore e in quello pessimo ha complessità O(n log n) .
Omissioni:
Il Merge Sort nel caso migliore e in quello pessimo ha complessità .
Modificato il 2006-03-02 21:05:12 da ViViana
Aggiunzioni:
Il Merge Sort nel caso migliore e in quello pessimo ha complessità .
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.
La versione più vecchia di questa pagina è stata modificata il 2006-03-02 21:04:26 da ViViana []
Vista della pagina:
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;
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’
Torna a Programmazione e Lab.
