DAA - Sắp xếp hợp nhất

Trong chương này, chúng ta sẽ thảo luận về sắp xếp hợp nhất và phân tích độ phức tạp của nó.

Báo cáo vấn đề

Vấn đề sắp xếp danh sách các số có nghĩa là ngay lập tức với chiến lược chia để trị: chia danh sách thành hai nửa, sắp xếp đệ quy từng nửa, rồi hợp nhất hai danh sách con đã sắp xếp.

Giải pháp

Trong thuật toán này, các số được lưu trữ trong một mảng numbers[]. Đây,pq đại diện cho chỉ số bắt đầu và kết thúc của một mảng con.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)
Function: Merge (numbers[], p, q, r)
n1 = q – p + 1 
n2 = r – q 
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
for i = 1 to n1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n2 
   rightnums[j] = numbers[q+ j] 
leftnums[n1 + 1] = ∞ 
rightnums[n2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

Phân tích

Chúng ta hãy xem xét, thời gian chạy Merge-Sort là T(n). Vì thế,

$ T (n) = \ begin {case} c & if \: n \ leqslant 1 \\ 2 \: x \: T (\ frac {n} {2}) + d \: x \: n & nếu không \ end {case} $ trong đó cd là hằng số

Do đó, sử dụng mối quan hệ lặp lại này,

$$ T (n) = 2 ^ i T (\ frac {n} {2 ^ i}) + idn $$

Như, $ i = log \: n, \: T (n) = 2 ^ {log \: n} T (\ frac {n} {2 ^ {log \: n}}) + log \: ndn $

$ = \: cn + dnlog \: n $

Do đó, $ T (n) = O (n \: log \: n) $

Thí dụ

Trong ví dụ sau, chúng tôi đã trình bày thuật toán Merge-Sort từng bước. Đầu tiên, mọi mảng lặp được chia thành hai mảng con, cho đến khi mảng con chỉ chứa một phần tử. Khi các mảng con này không thể được chia nhỏ hơn nữa, thì các phép toán hợp nhất được thực hiện.