선택 정렬 (Selection Sort)

선택 정렬

"가장 작은(또는 큰) 값을 선택해서 정렬하는 단순한 정렬 알고리즘"

• 리스트에서 가장 작은 값을 찾아 맨 앞 요소와 교환하는 방식
• 단순하지만 비효율적(O(n²)), 실무에서는 거의 사용되지 않음

---

선택 정렬 동작 원리

1. 리스트에서 가장 작은 값을 찾아 첫 번째 요소와 교환
2. 두 번째 요소부터 끝까지 탐색하여, 가장 작은 값을 찾아 두 번째 요소와 교환
3. 이 과정을 반복하여 리스트가 완전히 정렬될 때까지 수행

# Pseudo Code
FUNCTION SelectionSort(arr)
    FOR i FROM 0 TO length(arr) - 1
        min_index = i
        FOR j FROM i + 1 TO length(arr) - 1
            IF arr[j] < arr[min_index] THEN
                min_index = j
        END FOR
        SWAP arr[i] AND arr[min_index]
    END FOR
    RETURN arr
END FUNCTION


# Full Code
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):  # 총 n-1번 반복
        min_index = i  # 현재 탐색 범위에서 최소값의 인덱스 저장
        for j in range(i + 1, n):  # 현재 위치 이후의 값들과 비교
            if arr[j] < arr[min_index]:  # 더 작은 값을 찾으면 갱신
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]  # 최소값을 현재 위치로 이동
    return arr


# 테스트
arr = [5, 3, 8, 4, 2]
print("선택 정렬 결과:", selection_sort(arr))

---

선택 정렬의 시간복잡도

경우	시간복잡도
최선 (이미 정렬됨)	O(n²)
평균	O(n²)
최악 (역순 정렬)	O(n²)

 

❌ 모든 경우 O(n²) → 비효율적!

• 항상 리스트에서 최솟값을 찾는 과정(O(n))이 반복(O(n))
• 비교 연산이 많아서 정렬 속도가 느림

✅ 장점: 교환(Swap) 횟수가 적음

 

• 교환 횟수는 최대 n-1번으로, 버블 정렬보다 적음
• 메모리 이동 비용이 중요한 경우(하드웨어 구현 등)에는 버블 정렬보다 유리

---

선택 정렬의 장단점

장점

 

• 구현이 쉽고 직관적
• 추가 메모리 사용이 적음(O(1), 제자리 정렬)
• 교환 횟수가 적어 일부 환경에서는 유리

단점

• O(n²)로 비효율적 (입력 크기가 커지면 성능 저하 심각)
• 이미 정렬된 경우에도 O(n²) 시간이 걸림 → 개선 여지가 없음
• 퀵 정렬(O(n log n))이나 병합 정렬(O(n log n))보다 훨씬 느림

결론

선택 정렬은 이해하기 쉽지만, 성능이 좋지 않아 실무에서 거의 사용되지 않습니다. 대신 퀵 정렬(O(n log n)) 또는 병합 정렬(O(n log n)) 같은 더 효율적인 알고리즘을 사용합니다.