การจัดเรียงอาร์เรย์ของ 0, 1 และ 2 โดยใช้ C++

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

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

ตัวอย่างอินพุต 1

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

เอาต์พุต

0 0 1 1 2 2

คำอธิบาย

การจัดเรียงอาร์เรย์ที่กำหนดขององค์ประกอบที่มี 0, 1 และ 2 โดยใช้ DNF Sorting Algorithm จะพิมพ์เอาต์พุตเป็น {0, 0, 1, 1, 2, 2}

ตัวอย่างอินพุต 2

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

เอาต์พุต

0 0 1 1 1  1 2

วิธีการแก้ปัญหา

ในอาร์เรย์ที่กำหนดของ 0, 1 และ 2 เราสามารถใช้ DNF sorting algorithm ได้

DNF Sorting Algorithm - อัลกอริทึมต้องการ 3 ตัวชี้เพื่อวนลูปผ่านอาร์เรย์โดยการสลับองค์ประกอบที่จำเป็น

• สร้างตัวชี้ low ที่จุดเริ่มต้นของอาร์เรย์ และตัวชี้ high ชี้ที่ท้ายของอาร์เรย์
• หาจุดกลางของอาร์เรย์และสร้างตัวชี้ mid ที่วนลูปจากจุดเริ่มต้นของอาร์เรย์จนถึงท้าย
• ถ้าตัวชี้ mid ของอาร์เรย์เป็น '0' ให้สลับองค์ประกอบที่ชี้โดย low เพิ่มตัวชี้ low และ mid
• ถ้าตัวชี้ mid ของอาร์เรย์เป็น '2' ให้สลับกับองค์ประกอบที่ชี้โดย high เพิ่มตัวชี้ mid และลดตัวชี้ high
• ถ้าตัวชี้ mid ของอาร์เรย์เป็น '1' ให้เพิ่มตัวชี้ mid

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

#include <iostream>
using namespace std;

void dnfSort(int a[], int n) {
    int low = 0;
    int high = n - 1;
    int mid = 0;
    
    while (mid <= high) {
        if (a[mid] == 0) {
            swap(a[mid], a[low]);
            mid++;
            low++;
        } else if (a[mid] == 1) {
            mid++;
        } else if (a[mid] == 2) {
            swap(a[mid], a[high]);
            high--;
        }
    }
}

int main() {
    int a[] = {1, 0, 0, 2, 1, 1, 0, 0, 1};
    int n = sizeof(a) / sizeof(int);
    dnfSort(a, n);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

ผลลัพธ์

การรันโค้ดด้านบนจะสร้างเอาต์พุตเป็น

0 0 0 0 1 1 1 1 2