Java에서 0, 1 및 2의 배열을 정렬하는 방법

크기가 N인 0, 1, 2의 배열 A[]가 주어지면 작업은 0, 1, 2의 배열을 오름차순으로 정렬할 수 있는 함수를 작성하여 처음에 0이 있고 그 뒤에 모두 1이 오도록 하는 것입니다. 내부 또는 내장 정렬 기능이나 라이브러리를 사용하지 않고 끝에 2s가 있습니다.

예

Input: {0, 1, 2, 0, 1, 2}
Output: {0, 0, 1, 1, 2, 2}
Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
음, 0, 1, 2의 배열을 정렬할 수 있는 많은 접근 방식이 있을 수 있다는 사실을 부인할 수는 없지만, 이 블로그에서는 다른 모든 접근 방식 중에서 가장 좋고 가장 쉬웠다고 생각되는 3가지 접근 방식만 볼 것입니다. 구혼.

시작하자…

색인

무차별 대입 방식

계산 방식

3점 접근 방식 — 네덜란드 국기 접근 방식

무차별 대입 방식

이 접근 방식에서는 배열을 왼쪽에서 오른쪽으로 이동하면서 배열의 각 번호를 옆에 있는 번호와 비교할 것입니다. 외부 루프가 숫자를 추적하고 내부 루프가 배열의 나머지 요소와 비교하는 중첩 루프 시스템을 사용하여 이를 수행할 수 있습니다.

연산

i 및 j=i+1 요소에 대해 두 개의 루프를 사용합니다

.

i번째 요소가 j번째 요소보다 큰지 비교하여 확인합니다

.

그렇다면 오름차순으로 요소를 정렬해야 하므로 더 작은 요소가 먼저 오도록 위치를 바꿉니다.

어레이 인쇄

의사 코드

for(i=0 -> N)
{
   for(j=i+1 -> N)
   {
      if(A[i] > A[j])
      {
         Swap(A[i], A[j])
      }
   }
}
Print A

package com.Tekolio.Arrays;

import java.util.Arrays;

public class Sort_0s_1s_2s {
    public static void main(String[] args) {
        int[] A = {0, 1, 2, 0, 1, 2};
        int n = A.length;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                if(A[i] > A[j]) {
                    int temp = A[i];
                    A[i] = A[j];
                    A[j] = temp;
                }
            }
        }
        System.out.print(Arrays.toString(A));
    }
}

산출

A[] = [0, 0, 1, 1, 2, 2]

시간 복잡도 — O(N²) 공간 복잡도 — O(1)

우리 모두는 N log N에서 정렬 알고리즘의 time complexity을 알고 있지만 위의 접근 방식은 훨씬 더 높은 N²의 시간 복잡도를 사용합니다. 어떻게 O)N으로 최적화할 수 있는지 봅시다.

Continue Reading .