เราต้องใช้ three pointers: low, mid, high เราจะใช้ low และ mid pointers ที่จุดเริ่มต้น และ high pointer จะชี้ที่ปลายของอาร์เรย์ที่กำหนด
ถ้า array[mid] = 0 ให้สลับ array[mid] กับ array[low] และเพิ่ม pointers ทั้งสองทีละ 1
ถ้า array[mid] = 1 ไม่ต้องสลับ เพิ่ม mid pointer ทีละ 1
ถ้า array[mid] = 2 ให้สลับ array[mid] กับ array[high] และลด high pointer ลง 1
Time complexity - O(N)
ตัวอย่าง
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();
}
}
}ผลลัพธ์
0 0 0 0 1 1 1 1 2 2 2
