이론

선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방방법이다. 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 **O(n²)**으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않는다.

선택 정렬 수행 방식

<aside> 💡 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택 정렬의 핵심이다.

</aside>

문제

문제 설명

어떤 알고리즘을 사용해도 문제가 되지 않는다. 그러나 우리는 선택 정렬을 사용

문제 분석

슈도코드

구현

public class 내림차순으로자릿수정렬하기_1427 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        int[] A = new int[str.length()];
        for(int i=0; i<str.length(); i++) {
            A[i] = Integer.parseInt(str.substring(i, i+1));
        }

        // 선택 정렬 (내림차순)
        for(int i=0; i<str.length(); i++) {
            int MAX = i;
            //여기선 최댓값의 위치를 찾기만
            for(int j = i+1; j < str.length(); j++) {
                if(A[j] > A[MAX]) {
                    MAX = j;
                }
            }

            // swap
            if(A[i] < A[MAX]) {
                int temp = A[i];
                A[i] = A[MAX];
                A[MAX] = temp;
            }
        }

        for(int i=0; i<str.length(); i++){
            System.out.print(A[i]);
        }
    }
}