[알고리즘 / Java] 선택 정렬(Selection Sort)에 대해서

  컴퓨터 분야에서는 데이터를 얼마나 효율적이고 빠르게 정렬하는 것에 대한 이슈가 항상 발생해 왔습니다. 그렇기 때문에 정렬에 대한 알고리즘도 필연적으로 정렬을 해야하는 데이터에 따라 어느것이 더 효율적이고 시간 낭비 없이 해결되는지 항상 이슈화가 됐습니다.

  흔히 알고리즘 정렬 코드 종류는 버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬, 기수 정렬 등 다양한 코드들이 존재합니다. 그 중 간단하면서도 자주 쓰이는 알고리즘 정렬 코드로는 선택 정렬과 삽입 정렬이 있습니다. 이번 포스팅에서는 선택 정렬에 대한 알고리즘에 대해 알아보겠습니다.

  선택 정렬은 제자리 정렬로써 해당 위치[배열]에 들어갈 수를 전체와 비교하면서 정렬하는 방법입니다. 정렬은 오름차순인 경우와 내림차순인 경우에 따라 위치만 바뀔 뿐 전체적인 구조는 변하지 않습니다.

  선택 정렬은 일반적으로 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식입니다. 하나의 예시를 들어 설명해드릴께요.

기본 수	60	50	40	80	90	10	100	30	20
1회 순환	10	50	40	80	90	60	100	30	20
2회 순환	10	20	40	80	90	60	100	30	50
3회 순환	10	20	30	40	90	60	100	80	50
4회 순환	10	20	30	40	50	60	100	80	90
5회 순환	10	20	30	40	50	60	100	80	90
6회 순환	10	20	30	40	50	60	100	80	90
7회 순환	10	20	30	40	50	60	80	90	100
8회 순환	10	20	30	40	50	60	80	90	100

이처럼 선택 정렬의 경우는 이미 정렬이 끝났어도 전체의 수의 n - 1 만큼의 순회를 하게 됩니다. 이와 같은 알고리즘을 코드로 표현해 보겠습니다.

class SelectionSort {
    public static void main(String args[]) {
        int[] list = {1, 4, 3, 6, 10};
        int indexMin, temp;
 
        for (int i = 0; i < list.length - 1; i++) {
            indexMin = i;
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < list[indexMin]) {
                    indexMin = j;
                }
            }
            temp = list[indexMin];
            list[indexMin] = list[i];
            list[i] = temp;
        }
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}

위의 경우의 배열의 순서에 따라 차근차근 값을 비교하면서 값의 위치를 바꿔주는 코드를 표현한 것입니다. 위의 표처럼 가장 마지막의 배열은 굳이 검사할 필요가 없기 때문에 list.length - 1 만큼의 길이만큼만 순회하면서 temp라는 임시 변수에 값을 할당하고, 데이터 값의 대소비교를 통해 위치를 변경하는 코드입니다.