선택정렬

선택 정렬 (Selection Sort)

선택 정렬은 배열에서 최소값을 찾아 맨 앞의 원소와 교환하는 과정을 반복하여 정렬하는 알고리즘입니다.

핵심 요소

•

배열을 순회하며 최소값을 찾아 맨 앞부터 채워나가는 방식

•

두 개의 서브 리스트로 나누어 정렬 진행

•

제자리 정렬(in-place sorting) 알고리즘

시간 복잡도

최선의 경우	O(n²)
평균의 경우	O(n²)
최악의 경우	O(n²)

주요 특징

•

장점

◦

구현이 간단하고 이해하기 쉬움

◦

추가 메모리 공간이 거의 필요하지 않음

◦

안정적인 정렬 방식

•

단점

◦

시간 복잡도가 O(n²)으로 비효율적

◦

데이터 양이 많을수록 성능 저하

예시 코드

직접 구현

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n-1; i++) {
            int minIdx = i;
            
            // 최소값 찾기
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            // 최소값을 현재 위치와 교환
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}
Java
복사