ให้อาร์เรย์ 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' ให้เพิ่มตัวชี้กลาง
ตัวอย่าง
public class Solution {
public static void binarySorting(int arr[], int n){
int low=0;
int high= n-1;
int mid=0;
while(mid<=high){
if(arr[mid]==0){
int temp= arr[mid];
arr[mid]= arr[low];
arr[low]= temp;
mid++;
low++;
}
if(arr[mid]==1){
mid++;
}
if(arr[mid]==2){
int temp= arr[mid];
arr[mid]= arr[high];
arr[high]= temp;
high--;
}
}
}
public static void print(int arr[], int n){
for (int i = 0; i < n; i++)
System.out.print(arr[i] +" ");
}
public static void main(String[] args){
int arr[] ={ 0,0,1,0,1,0,1,2,2};
int n = arr.length;
binarySorting(arr, n);
print(arr, n);
}
} ผลลัพธ์
การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
0 0 0 0 1 1 1 1 2
