Tài liệu Pttktt_mergesort_thanhhuyen

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 ¿