선택 정렬 (Selection Sort)

선택 정렬은 가장 간단한 정렬 알고리즘 중 하나이다. 리스트에서 최소값을 찾아 맨 앞의 원소와 교체하는 방식으로 정렬을 수행한다.

선택 정렬은 구현이 간단하지만 시간복잡도가 O(n²)으로 효율성이 낮아 실제로는 거의 사용되지 않는다!

알고리즘 원리

선택 정렬의 기본 아이디어는 다음과 같습니다:

주어진 배열에서 정렬된 원소를 제외하고 최솟값을 찾는다.
찾은 최솟값을 정렬되지 않은 원소 중 맨 앞과 교환한다.
정렬된 부분을 제외한 나머지 원소들에 대해 같은 과정을 반복한다.
전체가 정렬될때까지 위 과정을 반복한다.

알고리즘 진행 예시

배열 [64, 34, 25, 12, 22, 11, 90]을 선택 정렬로 정렬하는 과정이다.

단계	배열 상태	설명
초기	`[64, 34, 25, 12, 22, 11, 90]`	정렬되지 않은 배열
Cycle 1	`[11, 34, 25, 12, 22, 64, 90]`	최솟값 11을 찾아 맨 앞과 교체
Cycle 2	`[11, 12, 25, 34, 22, 64, 90]`	정렬되지 않은 부분에서 최솟값 12를 찾아 두 번째 위치와 교체
Cycle 3	`[11, 12, 22, 34, 25, 64, 90]`	정렬되지 않은 부분에서 최솟값 22를 찾아 세 번째 위치와 교체
Cycle 4	`[11, 12, 22, 25, 34, 64, 90]`	정렬되지 않은 부분에서 최솟값 25를 찾아 네 번째 위치와 교체
Cycle 5	`[11, 12, 22, 25, 34, 64, 90]`	정렬되지 않은 부분에서 최솟값 34를 찾아 다섯 번째 위치와 교체
Cycle 6	`[11, 12, 22, 25, 34, 64, 90]`	정렬되지 않은 부분에서 최솟값 64를 찾아 여섯 번째 위치와 교체
Cycle 7	`[11, 12, 22, 25, 34, 64, 90]`	마지막 원소 90은 이미 올바른 위치이다.

구현 예시

Python 구현

def selection_sort(arr):
    n = len(arr)
    # 배열의 모든 원소를 순회
    for i in range(n):
        # 최솟값의 인덱스를 min_idx에 저장, 초기값: i
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 최솟값을 현재 가장 앞 원소와 교체
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# 사용 예시
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = selection_sort(arr)
print("정렬 전: ", arr)
print("정렬 후:", sorted_arr)

구현 자체는 어렵지 않다. 각 사이클에서 최솟값을 찾아 해당 위치와 교체하면 된다. 위의 예시는 오름차순으로 정렬하는 예시이다. 출력은 아래와 같습니다.

출력 결과

정렬 전: [64, 34, 25, 12, 22, 11, 90] 정렬 후: [11, 12, 22, 25, 34, 64, 90]

시간복잡도 분석

선택 정렬의 시간 복잡도를 분석해보자.

외부 루프는 (n-1)번 실행된다. (n-1)번 사이클이 종료되면, 마지막 원소는 자동으로 정렬되기 때문이다.
각 사이클에서 최솟값을 찾기 위해 (n-i)번 비교를 수행한다.
따라서 총 비교 횟수는 n(n-1)/2가 된다.
교환 횟수는 최대 (n-1)번이다. 각 단계에서 교환이 최대 한 번진행된다.

1, 2, 3, 4번에 의해 시간복잡도는 O(n²)임을 알 수 있다.

선택 정렬은 최선, 평균, 최악의 경우 모두 O(n²)의 시간복잡도를 가진다.

이미 정렬된 상태인 배열(최선의 경우)가 주어져도 각 사이클마다 정해진 횟수만큼 비교를 진행하기 때문이다.

특징

선택 정렬은 Unstable Sort이다.

선택 정렬은 In-place Sort이다.

Stable Sort와 In-place Sort에 대해서는 아래 글 참고

장단점

장점

구현이 간단하고 이해하기 쉽다.
교환 횟수가 적어 교환 비용이 높은 경우 유리함
In-place Sort

단점

시간 복잡도가 O(n²)로 비효율적
대용량 데이터에는 적합하지 않음
Unstable Sort, 같은 크기의 상대적 순서가 바뀔 수 있음

선택 정렬은 교육 목적으로는 훌륭하지만, 실제 프로젝트에서는 최적화된 함수를 제공하기 때문에, 그러한 함수를 사용하는 것이 좋다.

선택 정렬은 알고리즘을 이해하는데 매우 중요하다. 복잡한 알고리즘을 배우기 전에 이 선택 정렬부터 구현해보자!

버블 정렬
삽입 정렬
퀵 정렬
병합 정렬