선택 정렬 개요

선택 정렬 (Selection Sort) 은 정렬되지 않은 데이터 집합에서 가장 작은 (또는 큰) 값을 찾아 해당 위치로 이동시키는 반복적인 과정을 기반으로 합니다. 기본적으로 전체 데이터를 두 개의 영역으로 나눕니다. 하나는 이미 정렬이 완료된 부분이고, 다른 하나는 아직 처리되지 않은 미정렬 부분입니다.

동작 메커니즘

오름차순 정렬을 기준으로 설명하면 다음과 같은 절차가 따릅니다.

• 미정렬 영역 내에서 최솟값을 탐색합니다.
• 찾아낸 최솟값과 미정렬 영역의 첫 번째 요소와 자리를 바꿉니다.
• 정렬된 영역은 한 칸 뒤로 확장되고, 이 과정이 모든 원소가 정렬될 때까지 반복됩니다.

내림차순으로 정렬하고자 할 경우에도 동일한 논리를 적용하되, 최대값을 찾아 이동시키면 됩니다.

성능 특성 분석

선택 정렬의 효율성과 특성은 다음과 같이 요약할 수 있습니다.

• 시간 복잡도: 최선, 평균, 최악의 경우 모두 O(n²) 입니다. 배열의 크기가 n 일 때, 비교 횟수는 대략 n(n-1)/2 로 고정되어 입력 데이터의 초기 상태와 상관없이 동일한 연산량을 수행해야 합니다.
• 안정성 (Stability): 이 알고리즘은 불안정한 정렬에 속합니다. 동일한 값을 가진 요소들의 원래 상대적 순서가 교환 과정에서 변경될 수 있기 때문입니다.
• 공간 복잡도: 추가적인 메모리 공간 없이 기존 배열 내부에서 요소 교환만 일어나므로 O(1) 으로 매우 효율적입니다.
• 적용 시나리오: 데이터 양이 적거나 교환 연산 비용이 높은 환경 (예: 객체 참조 이동 대신 값 복사 시) 에서 유용하게 사용될 수 있습니다.

자바 코드 구현 예제

다음 코드는 난수를 생성하여 배열을 채운 후, 오름차순 선택 정렬을 수행하고 각 단계별 상태를 출력하는 예시입니다.

import java.util.Arrays;
import java.util.Random;

public class SelectionSortImplementation {

    private static final int ARRAY_SIZE = 6;

    public static void main(String[] args) {
        int[] numbers = generateRandomArray();
        
        System.out.println("초기 배열 상태: " + Arrays.toString(numbers));
        performSelectionSort(numbers);
        System.out.println("최종 정렬 결과: " + Arrays.toString(numbers));
    }

    /**
     * 난수를 사용하여 배열 초기화
     */
    private static int[] generateRandomArray() {
        Random randomSource = new Random();
        int[] data = new int[ARRAY_SIZE];
        for (int idx = 0; idx < data.length; idx++) {
            data[idx] = randomSource.nextInt(100); // 0 이상 100 미만
        }
        return data;
    }

    /**
     * 선택 정렬 알고리즘 실행
     */
    private static void performSelectionSort(int[] data) {
        int length = data.length;

        for (int i = 0; i < length - 1; i++) {
            int minIndex = i;

            // 현재 위치부터 끝까지 최소값 인덱스 찾기
            for (int j = i + 1; j < length; j++) {
                if (data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }

            // 최소값을 찾았다면 현재 위치와 교환
            if (minIndex != i) {
                int tempValue = data[i];
                data[i] = data[minIndex];
                data[minIndex] = tempValue;
                
                // 현재 스캔 상태 출력 (디버깅 목적)
                System.out.printf("%d 번째 패스: %s%n", i + 1, Arrays.toString(data));
            }
        }
    }
}

실행 결과 예시

코드 실행 시 콘솔에는 초기 배열과 정렬 과정 중 발생하는 상태 변화가 표시됩니다. 아래는 일부 샘플 출력 형태입니다.

초기 배열 상태: [45, 12, 78, 9, 33, 5]
1 번째 패스: [5, 12, 78, 9, 33, 45]
2 번째 패스: [5, 9, 78, 12, 33, 45]
3 번째 패스: [5, 9, 12, 78, 33, 45]
4 번째 패스: [5, 9, 12, 33, 78, 45]
5 번째 패스: [5, 9, 12, 33, 45, 78]
최종 정렬 결과: [5, 9, 12, 33, 45, 78]