Chuyên mục dịch vụ

thiết bị công nghệ

thiết bị công nghệ

Xuất xứ: TPHCM

Thương hiệu: dell

Lượt xem: 850

Divide and conquer là một trong số những mẫu thiết kế giải thuật chung được nhiều người biết đến nhất, và merge sort là một ứng dụng hay được tạo ra trên nền algorithm này. Trước khi đến với Merge Sort, chúng ta hãy tìm hiểu về Divide and Conquer.

Divide and conquer technique (typical case)

Các giải thuật devide and conquer hoạt động theo các bước sau:

1. Problem sẽ được chia thành nhiều cụm nhỏ, nên có kích thước bằng nhau.

2. Chúng ta sẽ xử lý tuần tử các problem nhỏ, đa số dùng đệ quy.

3. Trong một số trường hợp, kết quả của chúng sẽ được gộp để có kết quả.

divide and conquer

Một ví dụ đơn giản khi chúng ta muốn tính tổng n số hạng từ a0,… a(n-1) với điều kiện n>1. Chúng ta sẽ chia nhỏ bài toán thành hai bài toán nhỏ hơn: tính tổng từ đầu đến n/2 và từ n/2 hết phần còn lại. Và tiếp tục sử dụng đệ quy cho đến khi không thể chia nhỏ được nữa.

Giải thuật Merge Sort

Merge sort là một ví dụ của giải thuật divide and conquer này. Sau khi chia đủ nhỏ, merge sort sẽ gộp hai dữ liệu đã sort thành một dữ liệu lớn hơn.

merge sort

Theo hình trên, bạn có thể dễ dàng nhận ra cách chia nhỏ bài toán và gộp lại để cho ra kết quả.

Độ phức tạp của merge sort

Với n là số mũ của 2 và C(n) là số lần so sánh n phần tử, ta có:

 
C(n) = 2C(n/2) + Cmerge(n) for n>1, C(1) = 0
 

Tại sao như vậy?

Ví dụ: chúng ta cần sử dụng merge sort đế sort 8 chữ số sau theo thứ tự tăng dần:

Bước 1: Chia ra (divide)

Lần chia 1: 1 dãy số

 
108 15 50 4 8 42 23 16
 

Lần chia 2: 2 dãy số

 
(108 15 50 4) (8 42 23 16) 
 

Lần chia 3: 4 dãy số

 
(108 15) (50 4) (8 42) (23 16)
 

Lần chia 4: 8 dãy số

 
(108) (15) (50) (4) (8) (42) (23) (16)
 

Trong đó: C(n/2) là số so sánh chúng ta cần khi chia nửa số hạng, và cần 2 lần như vậy cho mỗi bước. Do đó ta có 2C(n/2)

Bước 2: Merge (conquer)

Lần gộp 1 - Số lần so sánh mỗi cặp tối đa: 1

 
(108) (15) (50) (4) (8) (42) (23) (16) 
 

Lần gộp 2 - Số lần so sánh mỗi cặp tối đa: 1

 
(15 108) (4 50) (8 42) (16 23) 
 

Lần gộp 3 - Số lần so sánh mỗi cặp tối đa: 4

 
(4 15 50 108) (8 16 23 32)
 

Ở bước này, xét trong hai cặp (15 108) và (4 50), merge sort sẽ lấy từng phần tử bé nhất của mỗi list (hoặc array) so sánh với nhau.

Cho A {15, 108} và B {4, 50}, các bước so sánh theo tuần tự:

15 và 4: 4 nhỏ hơn → {4} ; A {15, 108} ; B {50}

15 và 50: 15 nhỏ hơn → {4, 15} ; A {108} ; B {50}

108 và 50: 50 nhỏ hơn → {4, 15, 50} ; A {108} ; B {}

Chỉ còn 108 → {4, 15, 50, 108}

Tương tự với dãy array còn lại.

Lần gộp 4 - Số lần so sánh mỗi cặp tối đa: 8

 
(4 8 15 16 23 32 50 108)
 

Do vậy trong trường hợp xấu nhất, ta có n-1 lần so sánh.

Do đó ta có C(n) = 2C(n/2) + n -1 với n >1

Rút gọn lại: C(n) = 2C(n/2) + n

Giải theo Master Theorem, ta có kết quả O(nlogn)

Code của Merge Sort

 
procedure mergesort(1,r: integer);
var i, j, k, m : integer;
begin 
     if r-1>0 then 
         begin 
 m:=(r+1)/2; mergesort(1,m); mergesort(m+1,r);
  for i := m downto 1 do b[i] := a[j];
 for j :=m+1 to r do b[r+m+1-j] := a[j];
 for k :=1 to r do 
     if b[i] < b[j] then 
                begin a[k] := b[i] ; i := i+1 end
     else begin a[k] := b[j]; j:= j-1 end;
         end;
end; 
 

Ưu điểm và nhước điểm của Merge Sort

Ưu: Độ phức tạp tốt hơn so với Insertion Sort, Selection Sort, Interchange Sort

Nhược: Cần thêm bộ nhớ để chứa một mảng thứ 3

Bài viết được lấy từ đây: http://stream-hub.com/merge-sort

jasonmraz Địa chỉ:
Điện thoại: 0932765810
Fax:
Email: gintakao@gmail.com
Website:

BAMIEN
CHÀO BÁN
TÌM MUA
DỊCH VỤ
Tin tứcQuy địnhBảng giá QC
Góp ý
Loading