파이썬으로 배우는 선택 정렬(Selection Sort) — 개념부터 구현까지

선택 정렬(Selection Sort)이란?

이 글에서는 선택 정렬 알고리즘의 핵심 개념과 파이썬 3.x(그 이상 버전 포함)에서의 구현 방법을 단계별로 살펴보겠습니다.

선택 정렬은 배열을 정렬할 때, 아직 정렬되지 않은 부분에서 최솟값을 반복적으로 찾아 맨 앞으로 이동시키는 방식으로 동작합니다. 선택 정렬이 진행되는 동안 주어진 배열은 두 개의 하위 배열로 나뉩니다.

• 이미 정렬이 완료된 하위 배열
• 아직 정렬되지 않은 하위 배열

매 반복(iteration)마다 정렬되지 않은 하위 배열에서 최솟값을 꺼내어 정렬된 하위 배열의 끝에 삽입하는 것이 선택 정렬의 기본 원리입니다.

알고리즘의 시각적 표현

다음 그림은 선택 정렬이 배열을 순회하면서 최솟값을 찾아 교환하는 과정을 보여줍니다.

파이썬 구현 예제

A = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']

for i in range(len(A)):
    min_ = i
    for j in range(i + 1, len(A)):
        if A[min_] > A[j]:
            min_ = j
    # 스왑(swap)
    A[i], A[min_] = A[min_], A[i]

# 결과 출력
for i in range(len(A)):
    print(A[i])

실행 결과

a
i
l
o
r
t
t
u

위 코드를 실행하면 문자열 요소들이 오름차순으로 정렬된 결과를 확인할 수 있습니다. 여기서 min_ 변수는 현재 비교 중인 최솟값 후보의 인덱스를 저장하며, 내부 반복문을 통해 나머지 값들과 계속 비교됩니다.

알고리즘 성능 분석

선택 정렬의 주요 분석 지표는 다음과 같습니다.

시간 복잡도(Time Complexity) — O(n²)

보조 공간(Auxiliary Space) — O(1)

선택 정렬은 입력 크기와 관계없이 추가 메모리를 거의 사용하지 않는 제자리(in-place) 정렬 방식이라는 장점이 있습니다. 다만 데이터가 이미 정렬되어 있더라도 이중 반복문을 항상 수행하기 때문에 O(n²)의 시간 복잡도를 가지며, 이로 인해 대규모 데이터 처리에는 적합하지 않습니다.

아래 이미지처럼 코드가 실행되는 동안 모든 변수는 전역 프레임(global frame)에 선언됩니다.

결론

이번 글에서는 선택 정렬의 기본 개념과 작동 원리를 이해하고, 파이썬 3.x 환경에서 이를 직접 구현해 보았습니다. 선택 정렬은 구현이 간단하고 직관적이어서 정렬 알고리즘 학습의 첫걸음으로 매우 적합한 알고리즘입니다.