ด้วยอาร์เรย์ 0, 1 และ 2 ให้เรียงลำดับองค์ประกอบตามลำดับโดยที่ศูนย์ทั้งหมดมาก่อน 1 และ 2 ทั้งหมดในตอนท้าย เราต้องจัดเรียงองค์ประกอบทั้งหมดของอาร์เรย์ให้เข้าที่
เราสามารถแก้ปัญหานี้ได้โดยใช้อัลกอริทึมการจัดเรียง DNF (Dutch National Flag) ตัวอย่างเช่น
อินพุต-1 −
arr[ ]= {2,0,0,1,2,1 } ผลผลิต −
0 0 1 1 2 2
คำอธิบาย − การจัดเรียงอาร์เรย์ที่กำหนดขององค์ประกอบที่มี 0,1 และ 2 โดยใช้อัลกอริธึมการเรียงลำดับ DNF มันจะพิมพ์ผลลัพธ์เป็น {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 มันจะพิมพ์ผลลัพธ์เป็น {0,0,1,1,1,1,1,2}
แนวทางการแก้ปัญหานี้
ในอาร์เรย์ที่กำหนดเป็น 0, 1 และ 2 เราสามารถใช้อัลกอริธึมการเรียงลำดับ DNF ได้
อัลกอริธึมการเรียงลำดับ DNF − อัลกอริทึมต้องการตัวชี้ 3 ตัวเพื่อวนซ้ำทั่วทั้งอาร์เรย์โดยสลับองค์ประกอบที่จำเป็น
-
สร้างตัวชี้ต่ำที่จุดเริ่มต้นของอาร์เรย์และตัวชี้สูงที่ชี้ไปที่ส่วนท้ายของอาร์เรย์
-
ค้นหาจุดกึ่งกลางของอาร์เรย์และสร้างตัวชี้กลางด้วยซึ่งจะวนซ้ำตั้งแต่ต้นอาร์เรย์จนถึงจุดสิ้นสุด
-
หากตัวชี้กลางของอาร์เรย์เป็น '0' ให้สลับองค์ประกอบที่ชี้ไปที่ระดับต่ำ เพิ่มตัวชี้ต่ำและตัวชี้กลาง
-
หากตัวชี้กลางของอาร์เรย์คือ '2' ให้สลับกับองค์ประกอบที่ชี้ไปที่ระดับสูง เพิ่มตัวชี้กลางและลดตัวชี้สูง
-
หากตัวชี้กลางของอาร์เรย์คือ '1' ให้เพิ่มตัวชี้กลาง
ตัวอย่าง
#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++;
}
if(a[mid]==1){
mid++;
}
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
