Cho một mảng 0, 1 và 2, hãy sắp xếp các phần tử theo thứ tự sao cho tất cả các số không đứng trước 1 và cuối cùng là tất cả 2. Chúng ta phải sắp xếp tất cả các phần tử của mảng tại chỗ.
Chúng ta có thể giải quyết vấn đề này bằng cách sử dụng Thuật toán sắp xếp DNF (Quốc kỳ Hà Lan). Ví dụ:
Đầu vào-1 -
arr[ ]= {2,0,0,1,2,1 } Đầu ra -
0 0 1 1 2 2
Giải thích - Sắp xếp mảng đã cho gồm các phần tử chứa 0,1 và 2 bằng Thuật toán sắp xếp DNF, nó sẽ in ra kết quả là {0,0,1,1,2,2}.
Đầu vào-2 -
arr[ ]= {0,1,1,2,1,1,0} Đầu ra -
0 0 1 1 1 1 2
Giải thích - Sắp xếp mảng đã cho gồm các phần tử chứa 0,1 và 2 bằng Thuật toán sắp xếp DNF, nó sẽ in ra kết quả là {0,0,1,1,1,1,2}.
Phương pháp tiếp cận để giải quyết vấn đề này
Trong mảng 0, 1 và 2 đã cho, chúng ta có thể sử dụng thuật toán sắp xếp DNF.
Thuật toán sắp xếp DNF - Thuật toán yêu cầu 3 con trỏ lặp lại trong toàn bộ mảng bằng cách hoán đổi các phần tử cần thiết.
-
Tạo con trỏ thấp ở đầu mảng và con trỏ cao trỏ vào cuối mảng.
-
Tìm Điểm giữa của mảng và tạo một con trỏ ở giữa cũng như lặp lại từ đầu mảng cho đến cuối mảng.
-
Nếu con trỏ giữa của mảng là ‘0’, thì hãy hoán đổi phần tử trỏ xuống thấp. Tăng con trỏ thấp và con trỏ giữa.
-
Nếu con trỏ giữa của mảng là ‘2’, thì hãy hoán đổi nó với phần tử trỏ ở mức cao. Tăng con trỏ giữa và giảm con trỏ cao.
-
Nếu con trỏ giữa của mảng là ‘1’, thì hãy tăng con trỏ giữa.
Ví dụ
#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;
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
0 0 0 0 1 1 1 1 2