Selection Sort (선택 정렬)

선택 정렬(Selection Sort)은 단순하지만 비효율적인 정렬 알고리즘 중 하나이다. 주어진 배열에서 현재 위치에 저장될 값의 크기에 따라 최소 선택 정렬(오름차순)과 최대 선택 정렬(내림차순)로 나뉜다. 각 단계에서 최소값 또는 최대값을 찾아 현재 위치에 놓는 방식으로 정렬을 진행한다.

선택 정렬의 동작 원리

1. 기준 선택: 배열의 첫 번째 원소부터 시작하여 현재 위치를 기준으로 잡는다.
2. 최소값 찾기: 현재 위치 이후의 값 중에서 최소값을 찾는다.
3. 교환: 최소값과 현재 위치의 값을 교환한다.
4. 반복: 다음 위치로 이동하여 위의 과정을 반복한다.

예제 코드

public class SelectionSort {
    public static void sort(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; // 최소값의 인덱스 갱신
                }
            }
            // 최소값과 기준 위치의 값 교환
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;

            // 단계별 결과 출력
            print(arr, i + 1);
        }
    }

    private static void print(int[] arr, int step) {
        System.out.print(step + "단계 : ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

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

단계별 결과

1단계 : 1 6 2 4 3 9 7 
2단계 : 1 2 6 4 3 9 7 
3단계 : 1 2 3 4 6 9 7 
4단계 : 1 2 3 4 6 9 7 
5단계 : 1 2 3 4 6 9 7 
6단계 : 1 2 3 4 6 7 9 

시간 복잡도

선택 정렬의 시간 복잡도는 다음과 같다:

• 최악의 경우: O(N^2) - 모든 원소가 역순으로 정렬된 경우.
• 최선의 경우: O(N^2) - 배열이 이미 정렬된 경우에도 동일.
• 평균의 경우: O(N^2) - 일반적인 경우.

선택 정렬은 항상 두 개의 중첩 루프를 사용하여 각 원소를 비교하고 최소값을 찾는 구조이므로, 최선, 최악, 평균의 경우 모두 O(N^2)의 시간 복잡도를 가진다.

공간 복잡도

선택 정렬은 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 추가적인 메모리 공간이 필요하지 않다. 따라서 공간 복잡도는 O(1)이다.

장점

• 알고리즘이 단순하고 구현이 쉽다.
• 정렬을 위한 비교는 여러 번 수행되지만, 실제 교환 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• 시간 복잡도가 O(N^2)이므로 비효율적이다.
• 불안정 정렬(Unstable Sort)이다. 동일한 값의 원소 순서가 유지되지 않는다.

선택 정렬의 활용

선택 정렬은 단순한 알고리즘으로, 학습 목적으로 사용되거나 작은 데이터셋에 대해 사용할 수 있다. 그러나 큰 데이터셋에 대해서는 비효율적이므로 퀵 정렬, 합병 정렬 등 더 효율적인 정렬 알고리즘을 사용하는 것이 좋다.

So...

선택 정렬은 단순한 알고리즘으로, 작은 데이터셋이나 학습 목적으로 유용하다. 그러나 큰 데이터셋에 대해서는 비효율적이며, 불안정 정렬이기 때문에 동일한 값의 원소 순서가 유지되지 않는다. 오늘 학습을 통해 선택 정렬의 동작 원리와 장단점을 이해하고, 이를 적절히 활용할 수 있는 상황을 파악할 수 있었다.