선택 정렬(Selection sort)

선택 정렬(Selection sort)

선택 정렬은 자리를 선택한 다음, 거기에 맞는 원소를 찾아서 위치시킨다. 오름차순 정렬을 한다고 해보자. 첫 번째 자리엔 가장 작은 원소가 있어야 한다. 선택 정렬은 첫 번째 자리를 '선택'한 다음 원소 리스트를 순회하며 가장 작은 값을 찾아서 첫 번째 자리에 데려다놓는다. 그 다음 두 번째 자리를 선택하고 두 번째로 작은 원소를 찾는다. 이 작업을 원소 리스트의 크기 만큼 반복하는 것이 선택 정렬이다. 말하자면 선택한 장소에 마땅히 있어야 할 원소를 찾아서 제자리로 돌려보내는 것이다.

1. 최소값을 찾는다.

2. 그 값을 맨 처음 위치한 값과 바꾼다.

3. 제자리를 찾은 원소를 빼고 1, 2번을 반복한다.

선택 정렬은 원소 리스트를 한 번 순회할 때 하나의 원소만 정렬할 수 있다. n개의 원소를 정렬하려면 n번 순회해야 한다. 따라서 선택 정렬의 시간 복잡도는 O(n^2)로 성능이 나쁘다.

거품 정렬과 시간 복잡도가 같지만 자리를 바꾸는 일이 줄어들기 때문에 효율이 더 좋다.

거품 정렬도 그렇지만 배열 안에서 위치를 바꾸는 식으로 정렬하기 때문에 새로운 메모리를 필요로 하지 않는다(제자리 정렬). 따라서 메모리가 제한적일 경우 성능상 이점이 있을 수 있다.

선택 정렬 진행 과정

선택 정렬이 이루어지는 과정이다. 보다시피 이미 한 번 선택되었던 자리는 더 이상 비교할 필요가 없다. 첫 번째 자리부터 다음 자리로 이동하므로 원소의 수 - (n-1)번째 자리부터 비교하면 된다.

의사 코드

for i= 0 to n :
    a[i]부터 a[n-1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 한다.
    a[i]와 a[j] 값을 바꾼다.

코드로 Selection Sort 구현

public class Selection {
    public static void main(String[] args) {
        selectionSort(new int[]{5, 4, 8, 1, 3, 9, 2});
    }

    private static void selectionSort(int [] arr) {
        int minIndex;
        int temp;

        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;

            System.out.println(Arrays.toString(arr));
        }
    }
}

1. 맨 첫 번째 원소(minIndex)를 가장 작은 원소라고 가정하고 시작한다.
2. minIndex번째 자리에 있는 원소와 그 다음에 자리한 원소를 비교한다.
3. 만약, minIndex보다 다음 원소가 크다면 다음 원소가 minIndex가 된다.
4. 2 - 3번을 반복하면서 원소 리스트를 순회한다.
5. 순회가 끝나면 최종 minIndex로 결정된 원소를 맨 첫 번째 원소와 자리를 바꾼다.

selectionSort() 리팩토링

private static void selectionSort(int [] arr) {
    for (int selectIndex = 0; selectIndex < arr.length-1; selectIndex++) {
        //가장 작은 원소를 가진 index를 찾는다.
        int minIndex = findMinIndex(arr, selectIndex);
        //원소와 selectIndex의 원소 minIndex의 원소를 교환한다.
        swapElements(arr, minIndex, selectIndex);

        System.out.println(Arrays.toString(arr));
    }
}

private static int findMinIndex(int[] arr, int minIndex) {
    for (int j = minIndex + 1; j < arr.length; j++) {
        if (isLessThanMinIndex(arr[j], arr[minIndex])) {
            minIndex = j;
        }
    }
    return minIndex;
}

private static void swapElements(int[] arr, int minIndex, int selectIndex) {
    int temp;
    temp = arr[minIndex];
    arr[minIndex] = arr[selectIndex];
    arr[selectIndex] = temp;
}

private static boolean isLessThanMinIndex(int nextIndex, int minIndex) {
    return nextIndex < minIndex;
}

위에서 만든 selectionSort()메소드를 분기했다. 메소드의 흐름을 한눈에 파악할 수 있고, 복잡도도 떨어지는 것 같다.

일단 for문은 관례적으로 카운팅 변수를 i로 설정하지만 여기선 selectIndex으로 줬다. 이것은 카운트 변수가 하는 일을 좀 더 명확하게 보여주기 위함이다. 몇 번째 인덱스(selectIndex)를 선택했느냐가 선택 정렬에서는 굉장히 중요한 요소이므로 관례적인 i가 아닌 selectIndex로 해봤다. 이것이 좋은 코드인지는 아직 잘 모르겠다.

findMinIndex()는 입력 받은 배열을 minIndex부터 순회하면서 가장 작은 원소를 찾는다.

if문에 쓰인 isLessThanMinIndex의 원래 코드는 arr[j] < arr[minIndex]가 될 것이다. 이것이 무엇을 비교하는 코드인지 명확하게 해주기 위해서 nextIndex와 minIndex를 인자로 받아 비교하는 isLessThanMinIndex()메소드를 만들었다.