Cấu trúc dữ liệu và Giải thuật Bài 24: Thuật toán phân mảnh (Partitioning) trong mảng (Dutch National Flag).

Thay vì dùng chỉ mục để tìm kiếm hay tính toán như trong kỹ thuật Cửa sổ trượt, đôi khi chúng ta cần dùng chỉ mục để tổ chức lại toàn bộ không gian bộ nhớ. Một trong những thử thách kinh điển nhất về việc sắp xếp lại mảng chính là bài toán Dutch National Flag (Lá cờ quốc gia Hà Lan), được đề xuất bởi nhà khoa học máy tính vĩ đại Edsger W. Dijkstra (cha đẻ của thuật toán tìm đường đi ngắn nhất).

1. Bản chất của bài toán

Yêu cầu: Cho một mảng chứa $N$ phần tử, nhưng các phần tử này chỉ mang một trong ba giá trị phân biệt (ví dụ: 0, 1, và 2, tương ứng với 3 màu Đỏ, Trắng, Xanh của cờ Hà Lan). Hãy sắp xếp mảng sao cho các phần tử cùng màu đứng cạnh nhau theo đúng thứ tự 0, 1, 2.

Điều kiện ngặt nghèo: Phải thực hiện tại chỗ (In-place, không gian $O(1)$) và chỉ được duyệt qua mảng đúng một lần (One-pass).

Nếu không có điều kiện "một lần duyệt", phản xạ tự nhiên là dùng Counting Sort: Duyệt lần 1 để đếm xem có bao nhiêu số 0, số 1, số 2. Duyệt lần 2 để ghi đè các số đó vào mảng gốc. Tuy mất $O(n)$ thời gian, nhưng việc duyệt 2 lần sẽ cực kỳ kém hiệu quả nếu dữ liệu đến từ một luồng (Stream) không thể quay lui, hoặc kích thước mảng quá lớn gây ra các nhịp trễ IO trên bộ nhớ.

2. Cơ chế 3 con trỏ (3-Way Partitioning)

Dijkstra đã giải quyết bài toán này bằng cách thả 3 con trỏ cùng chạy trên mảng, chia mảng thành 4 phân khu (partitions) riêng biệt tại bất kỳ thời điểm nào:

1. low: Ranh giới an toàn của các số 0. Mọi thứ bên trái low chắc chắn là 0.

2. high: Ranh giới an toàn của các số 2. Mọi thứ bên phải high chắc chắn là 2.

3. mid: Con trỏ "trinh sát" đi khám phá mảng từ trái sang phải. Những phần tử nằm giữa mid và high là khu vực "chưa được khám phá" (Unknown).

Quy tắc vận hành:

Khởi tạo low = 0, mid = 0, và high = n - 1. Chừng nào mid <= high, con trỏ mid đọc dữ liệu và đưa ra 1 trong 3 quyết định:

• Nếu arr[mid] == 0: Đổi chỗ arr[mid] và arr[low]. Bây giờ số 0 đã an toàn ở đầu mảng. Cả low và mid cùng tiến lên 1 bước.

• Nếu arr[mid] == 1: Số 1 vốn dĩ phải nằm ở giữa. Không cần đổi chỗ, chỉ cần cho mid tiến lên khám phá tiếp.

• Nếu arr[mid] == 2: Đổi chỗ arr[mid] và arr[high]. Số 2 đã an toàn ở cuối mảng. Ta lùi high xuống 1 bước. Lưu ý: mid đứng im không tiến lên, vì phần tử vừa được hoán đổi từ high về mid vẫn là một phần tử ẩn số, cần được kiểm tra lại ở vòng lặp tiếp theo.

3. Triển khai thuật toán bằng Golang

Go

func sortColors(nums []int) {
    low := 0
    mid := 0
    high := len(nums) - 1

    for mid <= high {
        switch nums[mid] {
        case 0:
            // Quăng số 0 về nhóm bên trái
            nums[low], nums[mid] = nums[mid], nums[low]
            low++
            mid++
        case 1:
            // Để nguyên số 1 ở giữa, đi tiếp
            mid++
        case 2:
            // Quăng số 2 về nhóm bên phải
            nums[high], nums[mid] = nums[mid], nums[high]
            high--
            // Cảnh báo: Không được tăng mid ở đây!
        }
    }
}

Mô phỏng với mảng [2, 0, 2, 1, 1, 0]:

• Vòng 1 (mid = 0): nums[0] = 2. Đổi chỗ với high. Mảng thành [0, 0, 2, 1, 1, 2]. high giảm xuống. mid giữ nguyên.

• Vòng 2 (mid = 0): nums[0] = 0. Đổi chỗ với low (chính nó). Mảng không đổi. low tăng, mid tăng.

• Vòng 3 (mid = 1): nums[1] = 0. Đổi chỗ với low (chính nó). Mảng không đổi. low tăng, mid tăng.

• Vòng 4 (mid = 2): nums[2] = 2. Đổi chỗ với high (đang ở chỉ số 4). Mảng thành [0, 0, 1, 1, 2, 2]. high giảm. mid giữ nguyên.

• Sau vài nhịp xử lý gọn gàng số 1, thuật toán kết thúc với chỉ một vòng lặp $O(n)$ tuyệt đối.

4. Ứng dụng thực tế trong thiết kế phần mềm

Dù đề bài trông giống một trò chơi xếp màu, nhưng hạt nhân của nó mang lại giá trị to lớn cho các hệ thống thực tế:

• Tối ưu thuật toán Quick Sort (3-Way Quick Sort): Thuật toán Quick Sort tiêu chuẩn sẽ bị suy giảm hiệu năng nghiêm trọng (rơi xuống $O(n^2)$) nếu mảng chứa quá nhiều phần tử trùng lặp. Bằng cách áp dụng 3-Way Partitioning chia mảng thành: (1) Nhỏ hơn Pivot, (2) Bằng Pivot, (3) Lớn hơn Pivot, các phần tử trùng lặp được xử lý gọn gàng ở giữa, đưa tốc độ trả về $O(n \log n)$ ổn định.

• Phân luồng Log hệ thống (Log Bucketing): Khi bạn cần dồn một file log khổng lồ thành 3 mức độ nghiêm trọng INFO, WARN, ERROR trực tiếp trên bộ nhớ (In-memory) trước khi đẩy vào Elasticsearch mà không muốn tốn kém tài nguyên cấp phát mảng phụ.

Bài toán phân mảnh đã hướng dẫn cách duy trì trật tự của dữ liệu trong quá trình di chuyển. Ở bài học tiếp theo, chúng ta sẽ tiếp cận một thuật toán toán học khác để xử lý một hiện tượng dữ liệu cực kỳ dị biệt: Làm sao để tìm ra một phần tử chiếm ưu thế tuyệt đối trong hàng triệu bản ghi, mà không cần phải đếm tần suất của chúng?