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 정렬 알고리즘을 사용하여 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'이면 중간 포인터를 늘립니다.
예시
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