Cách sắp xếp mảng 0,1,2 (Cờ Quốc Gia Hà Lan) không dùng bộ nhớ thêm C#

Cần ba con trỏ low, mid, high. Low và mid ở đầu, high ở cuối.

• Nếu arr[mid] = 0: hoán đổi arr[mid] với arr[low], tăng cả low và mid.
• Nếu arr[mid] = 1: không hoán đổi, chỉ tăng mid.
• Nếu arr[mid] = 2: hoán đổi arr[mid] với arr[high], giảm high.

Độ phức tạp thời gian - O(N)

Ví dụ

using System;

namespace ConsoleApplication
{
    public class Arrays
    {
        private void Swap(int[] arr, int pos1, int pos2)
        {
            int temp = arr[pos1];
            arr[pos1] = arr[pos2];
            arr[pos2] = temp;
        }

        public void DutchNationalFlag(int[] arr)
        {
            int low = 0;
            int mid = 0;
            int high = arr.Length - 1;
            while (mid <= high)
            {
                if (arr[mid] == 0)
                {
                    Swap(arr, low, mid);
                    low++;
                    mid++;
                }
                else if (arr[mid] == 2)
                {
                    Swap(arr, high, mid);
                    high--;
                }
                else
                {
                    mid++;
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Arrays a = new Arrays();
            int[] arr = { 2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 1 };
            a.DutchNationalFlag(arr);
            for (int i = 0; i < arr.Length; i++)
            {
                Console.WriteLine(arr[i]);
            }
            Console.ReadLine();
        }
    }
}

Kết quả

0
0
0
0
1
1
1
1
2
2
2

Giải thích: Thuật toán Dutch National Flag (Dijkstra) sắp xếp mảng 3 giá trị {0,1,2} in-place một lần duyệt. Ba vùng: [0..low-1] chứa 0, [low..mid-1] chứa 1, [high+1..n-1] chứa 2. Mid duyệt qua vùng chưa xử lý.