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,p và q đạ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 đó c và d 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.