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

0, 1, 2로 구성된 배열이 주어지면 모든 0이 1보다 앞에 오고 모든 2가 맨 마지막에 오도록 요소를 정렬하세요. 배열의 모든 요소를 ​​제자리에서 정렬해야 합니다.

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

Input-1 -

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

Output -

0 0 1 1 2 2

Explanation − DNF 정렬 알고리즘을 사용하여 0, 1, 2가 포함된 배열을 정렬하면 {0, 0, 1,1,2,2}.

Input-2 −

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

Output -

0 0 1 1 1 1 2

Explanation − DNF 정렬 알고리즘을 사용하여 0, 1, 2를 포함하는 주어진 요소 배열을 정렬하면 {0,0,1, 1,1,1,2}.

이 문제를 해결하는 방법

주어진 0, 1, 2 배열에서 DNF 정렬 알고리즘을 사용할 수 있습니다.

DNF 정렬 알고리즘 − 이 알고리즘에는 전체 배열을 순회하고 필요한 요소를 교환하기 위해 3개의 포인터가 필요합니다.

• 배열의 시작 부분에 낮은 포인터를 만들고 배열의 끝을 가리키는 높은 포인터를 만듭니다.

• 배열의 중간점을 찾아 배열의 처음부터 끝까지 반복하는 중간점을 만듭니다.

• 배열의 중간 포인터가 '0'이면 낮은 포인터를 가리키는 요소를 바꿉니다. 낮은 및 중간 포인터를 추가했습니다.

• 배열의 중간 포인터가 '2'인 경우 높은 포인터를 가리키는 요소로 바꿉니다. 중간 포인터를 늘리고 높은 포인터를 줄입니다.

• 배열의 중간 포인터가 '1'이면 중간 포인터를 증가시킵니다.

Example

Demonstration

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);
   }
}

Output

위 코드를 실행하면 다음 출력이 생성됩니다.

0 0 0 0 1 1 1 1 2

위 내용은 Java를 사용하여 0, 1, 2의 배열 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!