Mô phỏng thuật toán Cờ ba màu (Dutch Flag)

Sort Colors (Dutch Flag) · Nhóm: Hai con trỏ

Cờ ba màu (Dutch National Flag): sắp mảng chỉ gồm 0, 1, 2 trong đúng một lượt bằng ba con trỏ low, mid, high.

Ý tưởng

Bất biến: [0, low) toàn 0, [low, mid) toàn 1, (high, n) toàn 2, phần chưa xét là [mid, high].

a[mid] = 0 thì đổi với low rồi tiến cả low và mid; a[mid] = 1 thì chỉ tiến mid; a[mid] = 2 thì đổi với high rồi lùi high (chưa tiến mid vì số vừa đổi về còn phải xét).

Vì sao đúng

Mỗi bước hoặc tiến mid hoặc lùi high nên phần chưa xét luôn thu hẹp, kết thúc sau một lượt duy nhất qua mảng.

Mã Python

def sort_colors(a):
    low, mid, high = 0, 0, len(a) - 1
    while mid <= high:
        if a[mid] == 0:
            a[low], a[mid] = a[mid], a[low]
            low += 1; mid += 1
        elif a[mid] == 1:
            mid += 1
        else:
            a[mid], a[high] = a[high], a[mid]
            high -= 1
    return a

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.