Mô tả:
SẮP XẾP HÒA NHẬP
1. Ý tưởng
Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer).
2. Thuật toán
3. Ví dụ
4. Thủ tục
5. Độ phức tạp
BÀI TẬP LỚN
Học phần: Phân tích và thiết kế thuật toán
Họ tên: Nguyễn Thị Thanh Huyền
Lớp: SP Tin K49
SẮP XẾP HÓA NHHOP̣P
1.
Y tưởng
Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải
thuật Chia để trị (Divide and Conquer).
Để sắp xếp một mảng A[start...end], Chúng ta sẽ chia mảng lớn
thành những mảng con nhỏ hơn bằng cách chia đôi mảng lớn và chúng
ta tiếp tục chia đôi các mảng con cho tới khi mảng con nhỏ nhất chỉ còn
1 phần tử. Sau đó chúng ta sẽ tiến hành so sánh 2 mảng con có cùng
mảng cơ sở (khi chúng ta chia đôi mảng lớn thành 2 mảng con thì mảng
lớn đó chúng ta gọi là mảng cơ sở của 2 mảng con đó) khi so sánh
chúng sẽ vừa sắp xếp vừa ghép 2 mảng con đó lại thành mảng cơ sở,
chúng ta tiếp tục so sánh và ghép các mảng con lại đến khi còn lại mảng
duy nhất thì đó là mảng đã được sắp xếp.
2.
Thuâ ̣t toản
Dãy chỉ gồm 1 phần tử được coi là đã sắp xếp tănng dần.
Giả sử cần sắp xếp dãy a[i..]] ta quy về viê ̣c sắp xếp 2 dãy con
a[i..k] và a[k+1..]] với k nằm ở giữa i và ] ( k=(i+]) div 2), sauđó ta hòa
nhâ ̣p 2 dãy đã được sắp xếp thành dãy được sắp xếp.
Thuâ ̣t toá hho ́hâ ̣p 2 dã đa đđươ c sp p xp
Giả sử có 2 dãy được sắp xếp, ta sẽ tìm cách hòa nhâ ̣p 2 dãy này lại
thành 1 dãy được sắp xếp
Ta sẽ đi so sánh 2 phầntử có giá trị nhỏ nhất của 2 dãy, chọn phần tử
nhỏ hơn đưa ra dãy sắp xếp riêng và loại phần tử đó ra khỏi dãy chca nó.
Lăn ̣p lại quá trình trên cho đến khi 1 trong 2 dãy hết thì chuyển dãy còn
lại vào đuôi của dãy sắp xếp.
3.
Ví dụ
Ví dụ: sắp xếp dãy sau theo phương pháp sắp xếp hòa nhâ ̣p: 12 2 5
1141
Dưới đây là các hình minh họa cách giải thuật sắp xếp trộn làm việc.
Giả sử chúng ta có mảng sau:
Đầu tiên, giải thuật sắp xếp trộn chia toàn bộ mảng thành hai nửa. Tiến
trình chia này tiếp tục diễn ra cho đến khi không còn chia được nữa và chúng
ta thu được các giá trị tương cng biểu diễn các phần tử trong mảng. Trong
hình dưới, đầu tiên chúng ta chia mảng kích cỡ 5 thành hai mảng kích cỡ 4.
Tiến trình chia này không làm thay đổi thc tự các phần tử trong mảng
ban đầu. Bây giờ chúng ta tiếp tục chia các mảng này thành 2 nửa.Tiến hành
chia tiếp cho tới khi không còn chia được nữa.
Bây giờ chúng ta tổ hợp chúng theo như đúng cách thcc mà chúng
được chia ra.
Đầu tiên chúng ta so sánh hai phần tử trong mỗi list và sau đó tổ hợp
chúng vào trong một list khác theo cách thcc đã được sắp xếp. Ví dụ:1 và 1 là
trong các vị trí đã được sắp xếp. 4 và 1 là trong các vị trí đã được sắp xếp.
Chúng ta so sánh 12 và 2 và trong list khác chúng ta đặt 2 ở đầu và sau đó là
12. Tươngtự, chúng ta thay đổi vị trí của 5 và
Vòng lặp tiếp theo là để kết hợp từng cặp list một ở trên. Chúng ta so
sánh các giá trị và sau đó hợp nhất chúng lại vào trong một list chca 4 giá trị,
và 4 giá trị này đều đã được sắp thc tự.
Sau bước kết hợp cuối cùng, danh sách sẽ trông giống như sau:
4.
Thủ tục
Thủ tụơ hho ́hâ ̣p 2 dã ơó o..kkā̀ và o.ā1.kk:̀.
Procedure Merge(var a: mang; i, ], k: Integer);
Var c: mang; t, h, i 1 , j1: Integer;
Begin
i 1 ≔i ; j 1:=k+1; t:=i;
while (i 1 ≤ k ¿ and¿ ¿) do
Begin
if a[i1 ¿ < a( j1 ) then
Begin
c[t]:= a[i1 ¿ ; inc(i 1 ¿;
End;
else
Begin
c[t]:= a[ j1 ¿ ; inc( j 1 ¿;
End;
inc(t);
End;
ifi1 ≤ k t h en
for h:= i1to k do
Begin
c[t] := a[h]; inc(t);
End;
if j 1 ≤ jt h en
for h:= j1 to ] do
Begin
c[t]:= a[h] ; inc(t);
End;
for t:= i to ] do a[t] := c[t];
End;
Thủ tụơ c sp p xp hho ́hâ ̣p
Procedure MergeSort( var a: mang; i,]: Integer);
Var k: Integer;
Begin
If i < ] then
Begin
k := ( i+]) div 2;
MergeSort( a, i, k);
MergeSort( a, k+1, ]);
Merge( a, i, k, ]);
End;
End;
5. Đô ̣ phưc ttap
0 ( 1 ) n ế u n=1
2T (n /2)+O ( n ) n ế u n>1
{
T(n)
T (n)= 2 T (n/ 2)+O ( n )
= O(n)+2[O(n/2) + 2 T(n /22 )¿
= 2 O ( n )+ 22 . T ¿)
= 2 O ( n )+ 22 . ¿)
=3 O ( n ) +23 . T ¿ )
= ….
=log 2 n . O ( n )+ 2log n .T (n /2log n )
2
2
= log 2 n . O ( n )+ 2log n .T (1)
2
= O(nlog 2 n ¿
- Xem thêm -