anonymous.rs

정렬 알고리즘: 선택 정렬 (Selection Sort)

5 min read

선택 정렬 (Selection Sort) 완벽 가이드

기초적인 정렬 알고리즘 중 하나인 **선택 정렬(Selection Sort)**에 대해 알아보겠습니다. 이름 그대로 ‘위치에 들어갈 원소를 선택’하여 정렬하는 직관적인 방법입니다.

1. 선택 정렬이란?

선택 정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘입니다. 오름차순 기준으로 배열에서 가장 작은 값을 찾아 맨 앞의 값과 교환하고, 그다음 작은 값을 찾아 두 번째 값과 교환하는 과정을 반복합니다.

2. 동작 과정 (오름차순 기준)

  1. 배열에서 최솟값을 찾습니다.
  2. 그 최솟값을 배열의 맨 앞에 위치한 값과 교환(Swap)합니다.
  3. 이제 맨 앞의 원소는 정렬이 완료된 상태가 됩니다.
  4. 정렬된 부분을 제외한 나머지 배열에서 다시 최솟값을 찾아 두 번째 자리와 교환합니다.
  5. 이 과정을 배열이 모두 정렬될 때까지 반복합니다.

3. 파이썬(Python) 구현 예시

def selection_sort(arr):
    n = len(arr)
    # 마지막 원소는 자동으로 정렬되므로 n-1번만 순회
    for i in range(n - 1):
        # 가장 작은 원소의 인덱스를 저장할 변수 (현재 인덱스로 초기화)
        min_idx = i
        
        # 정렬되지 않은 나머지 부분에서 최솟값 탐색
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                
        # 찾은 최솟값을 현재 위치(i)와 교환
        # (최솟값이 자기 자신인 경우 교환하지 않아도 되지만, 파이썬에서는 그냥 교환해도 무방)
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        
    return arr
 
# 사용 예시
data = [64, 25, 12, 22, 11]
print("정렬 전:", data)
print("정렬 후:", selection_sort(data))

4. 시간 복잡도 및 공간 복잡도

  • 시간 복잡도:
    • 최악, 최선, 평균: 모두 입니다. (데이터가 어떻게 정렬되어 있든 항상 전체 배열을 순회하며 최솟값을 찾아야 하기 때문입니다.)
  • 공간 복잡도: (주어진 배열 안에서만 교환이 일어나므로 추가 공간이 필요 없는 **제자리 정렬(In-place Sort)**입니다.)

5. 특징

  • 장점: 구현이 단순하고 직관적입니다. 또한 교환(Swap) 횟수가 전체 번만 발생하므로, 비교 횟수는 많지만 실제로 자리를 바꾸는 횟수는 적습니다.
  • 단점: 시간 복잡도가 무조건 이므로 효율성이 매우 떨어집니다. 또한, **불안정 정렬(Unstable Sort)**입니다. (예: [5(A), 5(B), 1]을 정렬하면 [1, 5(B), 5(A)]가 되어 같은 값의 상대적 순서가 바뀔 수 있습니다.)

요약

선택 정렬은 제자리를 찾아갈 값을 전체 탐색을 통해 ‘선택’하여 교환하는 방식입니다. 교환 횟수가 적다는 장점이 있지만, 항상 의 시간 복잡도를 가지고 불안정 정렬이라는 특징 때문에 실무에서는 잘 쓰이지 않습니다. 하지만 그 원리의 단순함 덕분에 알고리즘 기초 학습과 면접 질문으로 자주 활용됩니다.

Graph View