C++를 사용하여 0, 1, 2의 배열 정렬

0, 1, 2의 배열이 주어지면 모든 0이 1보다 먼저 오고 모든 2가 마지막에 오도록 순서대로 요소를 정렬합니다. 배열의 모든 요소를 ​​제자리에서 정렬해야 합니다.

DNF(Dutch National Flag) 정렬 알고리즘을 사용하여 이 문제를 해결할 수 있습니다. 예를 들어,

입력-1 -

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

출력 -

0 0 1 1 2 2

설명 − DNF Sorting Algorithm을 사용하여 0,1 및 2를 포함하는 요소의 지정된 배열을 정렬하면 출력이 {0,0,1,1,2,2}로 인쇄됩니다.

입력-2 -

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

출력 -

0 0 1 1 1 1 2

설명 − DNF 정렬 알고리즘을 사용하여 0,1 및 2를 포함하는 요소의 지정된 배열을 정렬하면 출력이 {0,0,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