선택정렬(Selection Sort)

선택정렬 (Selection Sort)

선택정렬은 루프를 돌면서 가장 작은 값부터 앞으로 차곡차곡 옮기는 것을 말한다.

선택정렬 과정

1. 위 배열이 있을 때 루프를 돌면서 가장 작은 값을 찾는다. 그리고 변수 idx에는 처음에 i값으로 초기화하고, 루프를 돌면서 가장 작은 값의 인덱스를 저장한다.
2. 루프가 끝나서 가장 작은 값을 찾으면 i번째인 첫 번째 위치한 8 과 가장 작은 값 2를 서로 swap한다. swap하게 되면 첫번째 원소는 정렬이 된 것이다. (초록색 부분)
3. 1과 2번의 과정을 반복한다. 역시 루프를 돌면서 가장 작은 값을 찾고 idx에는 가장 작은 값의 인덱스를 저장한다. 저장이 완료되면 i번째인 5와 가장 작은 값 5를 swap한다. 물론 이 결과는 그대로 있다.

위 과정을 계속 반복하게 되면 모든 정렬이 이루어진다. 코드를 보면 좀 더 이해하기 편하다.

import java.util.Arrays;

public class Ex01 {
    public static void main(String[] args) {
        int[] arr = {8, 5, 22, 11, 2};
        for (int i = 0; i < arr.length - 1; i++) { //i-1번 루프를 돈다.
            int idx = i; //가장 작은 값의 인덱스를 담는다.
            for (int j = i + 1; j < arr.length; j++) { //i+1번부터 끝까지 루프를 돈다.
                //j번 루프를 돌면서 가장 작은 값의 인덱스를 찾는 과정이다.
                if (arr[j] < arr[idx]) {
                    idx = j;
                }
            }
            //가장 작은 값을 찾은 후에는 서로 swap한다.
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }

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

선택정렬 시간복잡도

코드에서도 보았듯이 i번 돌면서 원소를 선택하고 그 안에 가장 작은 값을 저장하기 위해 또 루프를 돌기 때문에 O(N^2)이 걸린다. 쉽게 말해 2중 for문이므로 O(N^2)이 걸린다.

물론 한번의 과정을 맞추면 그 다음 과정은 전체에서 한번 뺀 만큼만 돌기 때문에 조금 단축되지만 빅오의 시간복잡도는 그정도는 단축된 것으로 치지도 않는다. (이 부분은 시간복잡도를 정리하면서 알아보겠다.)

재귀로 풀기

import java.util.Arrays;

public class Ex01 {
    private static void selectionSort(int[] arr) {
        selectionSort(arr, 0);
    }

    private static void selectionSort(int[] arr, int start) {
        if (start < arr.length - 1) { //마지막에서 1 뺀 만큼만 돈다.
            int idx = start;
            for (int i = start; i < arr.length; i++) {
                if (arr[i] < arr[idx]) {
                    idx = i;
                }
            }
            int tmp = arr[start];
            arr[start] = arr[idx];
            arr[idx] = tmp;
            selectionSort(arr, start + 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {8, 5, 22, 11, 2};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

위와 같이 재귀로 풀 수도 있다.
선택정렬이 어떤건지 이해만 하면 된다.

References

• 엔지니어 대한민국 - 선택정렬