Merge Sort

Chào các bạn! Tiếp theo chuỗi series về các thuật toán sắp xếp và tìm kiếm căn bản, thì ở bài viết này mình sẽ trình bày các bạn phần thuật toán Sắp xếp trộn - Merge Sort.

Không chậm chạp như Selection Sort, cũng không thất thường như cô nàng Quick Sort. Đây được đánh giá là một thuật toán mang tính ổn định cao. Độ phức tạp thuật toán luôn luôn $O(N*logN)$.

Hãy cùng tìm hiểu nó ngay sau đây nhé!

Đặt vấn đề

Quá quen thuộc rồi: Cho dãy số gồm $N$ phần tử, việc của bạn là sắp xếp chúng theo thứ tự tăng dần. Tất nhiên $N$ ứng với cả triệu số.

Ý tưởng thuật toán

Thuật toán có các bước sau đây:

1. Nếu dãy số có không quá 1 phần tử, thì coi như xong. Không cần làm gì nữa.
2. Nếu dãy số nhiều hơn 1 phần tử, thì chia dãy ra làm 2 phần bằng nhau
3. Sắp xếp 2 dãy con này
4. Gộp 2 dãy có thứ tự này thành dãy có kích thước ban đầu

Nhận xét: Sau khi đọc xong 4 bước ở trên, bạn có thấy ảo diệu không nào?

Giờ mình sẽ giải thích từ bước 2 trở đi nhé.

Chia dãy ra làm 2 phần bằng nhau

Việc này coi ra dễ, bạn chỉ cần cho rằng:

• Dãy thứ nhất bắt đầu từ left đến mid
• Dãy thứ hai là phần còn lại, bắt đầu từ mid + 1 đến right.

Ở đây, mid tương ứng là vị trí ngay giữa của dãy: mid = (left + right) / 2

Sắp xếp 2 dãy con này

Chỉ cần gọi đệ quy là được.

Ta đã biết rằng, nguyên tắc để có thể dùng đệ quy, ta cần đảm bảo 2 yếu tố:

1. Có tồn tại trường hợp thoát đệ quy
2. Có cách tổng hợp kết quả bài toán lớn, từ các bài toán con đệ quy

Thì ở đây, yếu tố thứ (1) ta đã có rồi - trường hợp thoát đệ quy của ta chính là khi dãy số có không quá 1 phần tử.

Còn yếu tố thứ (2) thì ta hãy cùng theo dõi tiếp bước tiếp theo nhé.

Gộp 2 dãy có thứ tự

Ta sẽ cùng giải quyết bài toán lớn này, thông qua một bài toán nhỏ hơn nào.

Bài toán: Cho 2 dãy số đã được sắp xếp tăng dần, hãy gộp chúng lại thành một dãy mới. Dãy mới phải đảm bảo cũng được sắp xếp tăng dần.

Cách giải quyết khá đơn giản, ta chỉ cần giải thuật $O(M + N)$ là có thể giải quyết được (với $N$ và $M$ là lần lượt là kích thước của 2 dãy con).

Dưới đây là đoạn code mẫu để giúp mình làm điều này:

void mergeParts(int *arr, int l, int mid, int r) { int i = l, j = mid + 1; int k = 0; while (i <= mid && j <= r) { int nextValue; if (arr[i] < arr[j]) nextValue = arr[i++]; else nextValue = arr[j++]; temp[k++] = nextValue; } while (i <= mid) temp[k++] = arr[i++]; while (j <= r) temp[k++] = arr[j++]; for (int i=0; i<k; i++) arr[l + i] = temp[i]; } 

Đoạn này, mình cần merge 2 đoạn có kích thước bằng nhau, và liên tục nhau.

• Đoạn 1: từ left đến mid
• Đoạn 2: từ mid + 1 đến right

Và temp chính là dãy số phụ để ta lưu lại kết quả trong khi merge.

Và dưới đây là code cho merge sort mà mình đã chuẩn bị:

void mergeSort(int *arr, int l, int r) { if (l >= r) return; int mid = (l + r) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); mergeParts(arr, l, mid, r);
} 

Full code bạn có thể xem ở đây: https://ideone.com/ej0MV8

Đánh giá độ phức tạp

Dễ thấy rằng, độ phức tạp của giải thuật trên là $O(N*logN)$ bất kể dãy số ban đầu có thứ tự như thế nào đi nữa.

Và nếu bạn nhấn vào link full code ở phía trên, không bất ngờ bạn cũng có thể tìm thấy dòng Memory + thời gian thực thi:

Success #stdin #stdout 0.19s 11316KB

Với thời gian thực thi không khác Quick Sort là bao với dãy số 1 triệu phần tử.