Python 선택 정렬(Selection Sort) 완벽 가이드: 원리부터 구현까지

이 글에서는 선택 정렬(Selection Sort) 알고리즘의 기본 개념과 Python 3.x 이상 버전에서의 구현 방법을 자세히 살펴보겠습니다.

선택 정렬이란 무엇인가?

선택 정렬은 정렬되지 않은 영역에서 최솟값을 반복적으로 찾아 배열의 맨 앞으로 옮기는 방식으로 전체 배열을 정렬하는 알고리즘입니다. 주어진 배열에 선택 정렬을 수행하면 실행 과정에서 두 개의 하위 배열(subarray)로 나뉩니다.

• 정렬된 하위 배열 — 이미 오름차순으로 정렬이 완료된 부분
• 정렬되지 않은 하위 배열 — 아직 정렬이 필요한 나머지 부분

선택 정렬의 매 반복(iteration)마다 정렬되지 않은 하위 배열에서 최솟값을 꺼내어 정렬된 하위 배열의 끝에 삽입하게 됩니다. 이 과정을 배열 전체가 정렬될 때까지 반복하는 것이 핵심 동작 원리입니다.

다음은 알고리즘의 동작 과정을 시각적으로 표현한 그림입니다.

Python으로 구현한 선택 정렬

이제 실제 코드를 통해 선택 정렬이 어떻게 구현되는지 확인해 보겠습니다.

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]
# main
for i in range(len(A)):
    print(A[i])

실행 결과

a
i
l
o
r
t
t
u

코드 동작 원리 분석

실행 결과를 보면 알고리즘이 문자열 배열을 오름차순으로 성공적으로 정렬한 것을 확인할 수 있습니다. 여기서 min_ 변수는 현재 비교 대상이 되는 값의 인덱스를 저장하며, 내부 반복문을 돌면서 다른 모든 값들과 비교하여 더 작은 값을 발견하면 해당 인덱스로 갱신됩니다. 한 번의 순회가 끝나면 최솟값이 확정되고, 현재 위치의 요소와 스왑(swap)됩니다.

알고리즘 성능 분석

선택 정렬의 성능 지표는 다음과 같습니다.

시간 복잡도(Time Complexity) — O(n²)
배열의 크기가 n일 때, 모든 요소를 서로 비교해야 하므로 이중 반복문 구조로 인해 n²에 비례하는 연산 횟수가 발생합니다.

보조 공간(Auxiliary Space) — O(1)
추가적인 메모리 사용 없이 제자리(in-place) 정렬이 이루어지므로 공간 효율성이 뛰어납니다.

아래 이미지에서 볼 수 있듯이, 모든 변수는 전역 프레임(global frame)에 선언되어 관리됩니다.

결론

이번 글에서는 선택 정렬의 기본 개념과 동작 원리를 이해하고, Python 3.x 환경에서 직접 구현하는 방법까지 살펴보았습니다. 선택 정렬은 구현이 간단하고 추가 메모리가 거의 필요 없다는 장점이 있지만, 시간 복잡도가 O(n²)이기 때문에 대규모 데이터에는 적합하지 않습니다. 따라서 학습용이나 소규모 데이터 정렬에 활용하기에 적합한 알고리즘입니다.