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)