[알고리즘 구현] Java로 선택 정렬 알고리즘 구현하기

알고리즘을 시작하면 대부분의 책에 가장 앞에서 소개되는 Selection Sort. 선택 정렬에 대해서 알아보자.

선택 정렬

선택 정렬은 배열의 원소 중 가장 작은(큰) 값을 배열의 끝으로 보내는 작업을 반복하는 알고리즘이다.

간단한 컨셉인 만큼 효율성은 떨어질 수 있으나 적은 양의 데이터에서는 효과적일 수 있다.

정렬 과정

1. 주어진 리스트에서 최소값을 찾기
2. 그 값을 맨 앞의 값과 교체
3. 처음 맨 위치를 뺀 나머지를 위와 같은 방법으로 교체

의 과정으로 정렬이 이루어진다.

생각해보자.

만약 [9, 1, 6, 8 ,4, 3, 2, 0] 이라는 배열이 있다고 생각해보자.

1. 배열 : [9, 1, 6, 8, 4, 3, 2, 0] 최소값 : 0
2. 배열 : [0, 1 ,6 ,8 ,4 ,3 ,2, 9] 최소값 : 1
3. 배열 : [0, 1, 6, 8, 4, 3, 2, 9] 최소값 : 2
4. 배열 : [0, 1, 2 ,8 ,4 ,3 ,6 ,9] 최소값 : 3
5. 배열 : [0, 1 ,2, 3, 4, 8, 6, 9] 최소값 : 6
6. 배열 : [0, 1, 2, 3 ,4 ,8 ,6 ,9] 최소값 : 8
7. 배열 : [0, 1, 2 ,3, 4, 6, 8, 9]

실행 시간

n^2의 실행 시간

구현 하기

우선 구현하기 앞서 메서드를 먼저 생각해보자.

위의 과정을 보면 우리는 첫 번째로 주어진 배열의 최소 값을 찾는 메서드를 만들어야 하고, 두 번째로 해당 인덱스와 첫 번째 인덱스를 변경하는 메서드를 만들어야 한다.

또한 정렬이 끝난 인덱스는 건너 뛰어야 한다.

그럼 3개의 메서드를 만들면 될 것으로 보인다.

 

1. 배열 최소값 찾는 findLowestIndex() 메서드
2. 인덱스끼리 값을 변경하는 swap() 메서드
3. 실질적으로 정렬이 되는 selectionSort() 메서드

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {6, 8, 9, 2, 5, 1, 4, 3, 7, 0};

        /*
        * 1. 배열 인덱스 최솟값 찾기
        * 2. 배열 인덱스 첫번째 값과 변경*/

        selectionSort(arr);

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

    private static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }

    private static int findLowestIndex(int[] arr, int start) {
        int lowest = start;
        for (int i = start; i < arr.length; i++) {
            if(arr[lowest] > arr[i]) {
                lowest = i;
            }
        }
        return lowest;
    }

    private static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int targetIndex = findLowestIndex(arr, i);
            swap(arr, i, targetIndex);
        }
    }
}

전체 소스 코드는 다음과 같다.

 

swap()

private static void swap(int[] arr, int idx1, int idx2) {
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}

간단하고 잘 알려진 swap() 메서드이다.

특별한 설명 없이 넘어가겠다.

 

findLowestIndex

private static int findLowestIndex(int[] arr, int start) {
    int lowest = start;
    for (int i = start; i < arr.length; i++) {
        if(arr[lowest] > arr[i]) {
            lowest = i;
        }
    }
    return lowest;
}

해당 메서드에서는 arr[] 배열과 시작 인덱스 위치인 start 변수를 받는다.

최초 가장 작은 수를 갖고있는 arr 배열의 인덱스를 start 변수로 지정해주고, arr의 길이 만큼 반복을 돌며 arr[lowest]와 반복 인덱스인 arr[i]와 비교해서 더 작은 값을 갖고 있는 인덱스가 새로운 lowest 변수에 담기게 된다.

 

SelectionSort

우리는 지금까지 가장 작은 인덱스를 찾았고, 가장 작은 인덱스와 배열 첫 번째 인덱스를 변경시켜주는 메서드까지 만들었다.

 

이제 실질적으로 반복을 돌며 정렬을 수행할 메서드를 만들어 보자.

private static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int targetIndex = findLowestIndex(arr, i);
        swap(arr, i, targetIndex);
    }
}

반복을 arr의 0번째 인덱스만큼 돌며 0번째 인덱스를 시작으로 findLowestIndex와 swap을 차례대로 실행한다.

그리고 첫 번쨰 반복이 끝나면 arr의 0번째 인덱스의 값에는 주어진 배열의 최소값을 담고 있으므로 해당 인덱스만 제외시킨 후 다시 iteration을 돈다.