선택 정렬 (Select Sort)

선택 정렬은 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.

오름차순을 기준으로 정렬한다.

개념

제자리 정렬의 알고리즘 중 하나이다.

정렬 되지 않은 입력된 배열 외에 다른 메모리를 사용하지 않는다.

해당하는 n번째에 넣을 정렬된 원소 자리는 이미 정해져있고,

어떤 값을 넣을지를 선택하는 알고리즘이다.

동작 과정

1. 주어진 배열에서 최솟값을 찾는다.
2. 그 최솟값을 배열의 맨 앞의 수와 자리를 교체해준다.
3. 맨 처음 값을 뺀 나머지 배열로부터 최솟값을 찾는다.
4. 교체한 다음 맨 앞의 배열과 값을 바꿔준다.
5. 이 과정을 정렬이 완료될 때까지 계속 반복한다.

보기 좋은 예시 이미지를 가져와봤다.

이제 그러면 구현을 해보도록 하자.

Select Sort 구현

n 길이를 가진 배열을 생성하고 다음줄에 n개의 숫자를 입력받아 선택정렬 한다.

public class SelectionSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); //길이가 n
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int[] arr = new int[n]; //n개의 숫자를 넣을 배열
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        final int[] results = solution(arr);
        
        for (int result : results) {
            System.out.print(result);
        }
    }
    
    private static int[] solution(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            //최소값과 해당 반복 index의 맨 앞자리와 치환
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }
}

결론

이런 사소한 지식이라도 안적어두면 까먹고 또 기억이 안나는것 같다.

위의 예시도 ide도움 없이 손코딩으로 포스팅을 올려보는데 더 상기되서 까먹지 않을것 같다.

계속 까먹기 때문에 이렇게 기록으로 남겨두는것이 좋을듯 하다. 😎