จัดเรียงอาร์เรย์ของ 0, 1 และ 2 ด้วยอัลกอริทึม Dutch National Flag ใน Java

กำหนดให้มีอาร์เรย์ที่ประกอบด้วยตัวเลข 0, 1 และ 2 ให้จัดเรียงองค์ประกอบให้เรียงลำดับโดยที่ 0 ทั้งหมดอยู่หน้าสุด ตามด้วย 1 และ 2 อยู่ท้ายสุด โดยต้องจัดเรียงแบบ in-place (ไม่ใช้พื้นที่เพิ่ม)

สามารถแก้ปัญหานี้ได้ด้วย DNF (Dutch National Flag) Sorting Algorithm ตัวอย่าง:

Input-1

arr[] = {2, 0, 0, 1, 2, 1}

Output

0 0 1 1 2 2

Input-2

arr[] = {0, 1, 1, 2, 1, 1, 0}

Output

0 0 1 1 1 1 2

แนวทางแก้ปัญหา: DNF Sorting Algorithm

อัลกอริทึม DNF ใช้ 3 pointer ในการวนลูปและสลับองค์ประกอบ:

• low pointer - ชี้ที่ต้นทางของอาร์เรย์
• high pointer - ชี้ที่ปลายทางของอาร์เรย์
• mid pointer - เริ่มต้นที่ต้นทางและเคลื่อนไปจนถึง high

ขั้นตอนการทำงาน

1. ถ้า arr[mid] == 0: สลับกับ arr[low] แล้วเพิ่ม low และ mid
2. ถ้า arr[mid] == 1: เพิ่ม mid เท่านั้น
3. ถ้า arr[mid] == 2: สลับกับ arr[high] แล้วลด high (mid ไม่เพิ่ม เพราะต้องตรวจสอบค่าใหม่ที่สลับมา)

ทำซ้ำจนกว่า mid > high

ตัวอย่างโค้ด

public class Solution {
    public static void dnfSort(int[] arr, int n) {
        int low = 0;
        int high = n - 1;
        int mid = 0;

        while (mid <= high) {
            if (arr[mid] == 0) {
                // สลับ arr[mid] กับ arr[low]
                int temp = arr[mid];
                arr[mid] = arr[low];
                arr[low] = temp;
                mid++;
                low++;
            } else if (arr[mid] == 1) {
                mid++;
            } else { // arr[mid] == 2
                // สลับ arr[mid] กับ arr[high]
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

    public static void printArray(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {0, 0, 1, 0, 1, 0, 1, 2, 2};
        int n = arr.length;
        dnfSort(arr, n);
        printArray(arr, n);
    }
}

ผลลัพธ์

0 0 0 0 1 1 1 1 2 2

ความซับซ้อน

• Time Complexity: O(n) - ผ่านอาร์เรย์เพียงครั้งเดียว
• Space Complexity: O(1) - ใช้พื้นที่คงที่