10) Trình bày giải thuật sắp xếp hòa nhập (Merge Sort)? Trình bày thời gian thực hiện giải thuật với dãy n phần tử. Minh họa diễn biến ở từng bước khi áp dụng giải thuật này với dãy số: 34, 15, 74, 11, 65, 58, 83, 36, 88, 99.
Bài làm:
Hòa nhập 2 đường
Procedure Merge(X, b, m, n, Z);
i := b j := m+1; k := b; //Khởi tạo các chỉ số
While (i<m) and (j<n) do //So sánh để chọn phần tử nhỏ hơn
Begin
If X[i] < X[j] then
Begin
Z[k] := X[i; i:= i+ 1;
End;
Else
Begin
Z[k] := X[j]; j := j+1;
End;
k := k+1;
End;
If i > m then
(Z[k],…,Z[n]) := (X[j],…,X[n])
Else //Đoạn sau hết phần tử
(Z[k],…,Z[n]) := (X[i],…,X[m])
Return;
Hòa nhập 2 đường trực tiếp
Thủ tục sắp xếp hòa nhập từng cặp mạch kề cận:
Procedure MPass(X,Y,n,k)
i := 1;
While i =< n – 2k+ 1 do //Vẫn còn đủ 2 mạch ở phía sau
Begin
Merge (X, i, i + k- 1, i + 2k – 1, Y);
i := i + 2k;
end;
//Hòa nhập mạch còn lại có độ dài tổng >k, <2k
If i + k – 1 < n then
Merge(X, i, i + k – 1, n);
Else //Chỉ còn 1 mạch cuối cùng
(Y[i],…,Y[n]) := (X[i],…,X[n]);
Return;
Thủ tục sắp xếp hòa nhập
Procedure Straight_Msort (X,n);
k := 1;
While k < n do
Begin
MPass (X, Y, k); k := 2*k;
MPass (Y,X,k); k := k*2;
End;
Return;
Thời gian thực hiện giải thuật:
Dễ nhận thấy phép chuyển đổi chỗ nhiều hơn phép so sánh do vậy ta chọn phép đổi chỗ làm phép toán tích cực.
Ta thấy mỗi khi gọi đến MPass thì toàn bộ các phần tử của mảng được duyệt qua 1 lần và chuyển sang 1 vùng mới từ X sang Y hoặc từ Y sang X. Do vậy MPass có cấp độ thực hiện thời gian là O(n)
Số lần gọi MPass chính là log2n
=> Độ phức tạp O(nlog2n)
