선택 정렬(Selection Sort)

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법

 

시간 복잡도: O(N^2)

 

최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것

 

📌 정렬 과정

 

1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap
3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소
4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복 (반드시 N^2만큼 수행하므로 시간 복잡도를 줄이기 힘들다)

 

 

📌 알고리즘

 

public class SelectionSort {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] N = br.readLine().split("");
        int[] A = new int[N.length];
        StringBuilder sb = new StringBuilder();
        int max;

        for (int i = 0; i < A.length; i++) {
            A[i] = Integer.parseInt(N[i]);
        }

        //선택 정렬
        for (int i = 0; i < N.length - 1; i++) {
            max = i;
            for (int j = i + 1; j < N.length; j++) {
                if (A[max] < A[j]) max = j;
            }
            int tmp = A[i];
            A[i] = A[max];
            A[max] = tmp;
        }

        for (int i = 0; i < N.length; i++) {
            sb.append(A[i]);
        }

        System.out.println(sb);
    }

}

 

Reference: