선택 정렬

목표 

가끔 코딩 테스트 문제를 풀다가 정렬에 대한 문제가 나오는데, 
헷갈릴 때가 많다. 항상 헷갈리는 이유중 하나가 왜 선택 정렬이고 왜 삽입 정렬이고 이런 생각을 안해봐서 그렇다.
그래서 이번 기회에 선택 정렬, 버블 정렬 , 삽입 정렬에 대해서 
공부하고 정리해 보려고 한다. 
그 중 선택 정렬에 대해 간단히 정리해 보았다.

 

선택 정렬 

현재 인덱스에 들어갈 값을 선택하는 정렬

즉, 루프를 돌면서 해당 인덱스에 올 데이터를 선택하는 정렬이다.

선택정렬을 사용하여 오름차순으로 정렬 할 때,
첫번째 인덱스에 올 데이터는 어떻게 구해야 할까?

 

크기가 100 개 인 경우, 첫번째 인덱스를 제외한 나머지 숫자들 중 가장 작은 숫자를 구하고 

구한 수 ( 12 ) 와 현재 첫번째 인덱스에 있는 수를 비교하여
작은 값을 넣어 주면 된다.

이런 행동을 마지막 인덱스 까지 반복하면 된다. 
회차가 지날 수록 조회 해야하는 수가 줄어든다.

 시간 복잡도를 계산 해보면 

코드로 구현 해 보자

    public static void main(String[] args) throws IOException {

        BufferedReader br       = new BufferedReader(new InputStreamReader(System.in));
        int arrSize             = Integer.parseInt(br.readLine());
        int[]          arr      = new int[arrSize];


        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for( int i = 0; i < arrSize; i++)
        { arr[i] = Integer.parseInt(st.nextToken()); }

        for(int i = 0 ; i<arrSize-1; i++)
        {
            int minIdx = i;
            for(int j = i+1; j<arrSize; j++)
            {
                if(arr[j] < arr[minIdx] ) minIdx = j;
            }

            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }


        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

입력 값 

10
112 212 32 5 1 543 6 75 23 13

 

출력 값 

1 5 6 13 23 32 75 112 212 543

 

후기 

어쩌다가 한번씩 풀어보는 정렬 문제여서 그렇게 깊게 찾아보지도 않았다.
해당 인덱스에 오는 값들을 선택하는 것을 굳이 강조하여 머리에 욱여 넣었지만 
덕분에 기억에 오래 남을 것 같다.