선택 정렬

정렬이란?

자료의 크기 순서대로 맞춰 일렬로 나열하는 것을 정렬이라고 한다. 사전의 경우 단어를 가나다순 혹은 알파벳순으로 나열했으므로 정렬의 좋은 예시라고 할 수 있다.
리스트에 들어있는 숫자를 크기순으로 나열하는 정렬 알고리즘의 입출력은 아래와 같이 정리할 수 있다.

• 문제: 리스트 안에 있는 자료를 순서대로 배열하기
• 입력: 정렬할 리스트 (예: [35, 9, 2,85, 17])
• 출력: 순서대로 정렬된 리스트 (예: [2, 9, 17, 35, 85])

사실 '그냥 적당히 순서대로 적으면 되지 않나?' 라는 생각이 들 수 있지만, 정렬 문제를 푸는 방법과 분석만 모아도 두꺼운 책이 한 권 나올 정도로 실제로는 다양한 정렬 알고리즘이 있으며 알고리즘에 따라 계산 복잡도나 특징도 다르다.

정렬 알고리즘에는 대표적으로 5가지가 있다.

1. 선택 정렬 (Selection sort)
2. 삽입 정렬 (Insertion sort)
3. 병합 정렬 (Merge sort)
4. 퀵 정렬 (Quicksort)
5. 버블 정렬 (Bubble sort)

이 중에서 선택정렬을 좀 더 집중적으로 다뤄보자!

쉽게 설명한 선택 정렬 알고리즘

# 쉽게 설명한 선택 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
# 주어진 리스트에서 최솟값의 위치를 돌려주는 함수

def find_min_idx(a):
    n = len(a)
    min_idx = 0 # idx = index
    for i in range(1, n):
        if a[i] < a[min_idx]:
            min_idx = i
    return min_idx

def sel_sort(a):
    result = [] # 새 리스트를 만들어 정렬된 값을 저장
    while a: # 주어진 리스트에 값이 남아 있는 동안 계속
        min_idx = find_min_idx(a) # 리스트에 남아 있는 값 중 최솟값의 위치
        value = a.pop(min_idx) # 찾은 최솟값을 빼내어 value에 저장
        result.append(value) # value를 결과 리스트 끝에 추가
    return result

d = [2, 4, 5, 1, 3]
print(sel_sort(d))

위 코드를 단계적으로 생각해보자.

1. 시작
   a = [2 4 5 1 3]
   result = []

2. a 리스트의 최솟값인 1을 a에서 빼내어 result에 추가한다.
   a = [2 4 5 3]
   result = [1]

3. a에 남아 있는 값 중 최솟값인 2를 a에서 빼내어 result에 추가한다.
   a = [4 5 3]
   result = [1 2]

4. a에 남아 있는 값 중 최솟값인 3을 같은 방법으로 옮긴다.
   a = [4 5]
   result = [1 2 3]

5. a에 남아 있는 값 중 최솟값인 4를 같은 방법으로 옮긴다.
   a = [5]
   result = [1 2 3 4]

6. a에 남아 있는 값 중 최솟값인 5를 같은 방법으로 옮긴다.
   a = []
   result = [1 2 3 4 5]

7. a가 비어 있으므로 종료한다.
   result = [1 2 3 4 5] -> 최종 결과

일반적인 선택 정렬 알고리즘

선택 정렬의 원리를 좀 더 효율적으로 구현한 프로그램을 살펴보자. '일반적인 선택 정렬 알고리즘'은 입력으로 주어진 리스트 a 안에서 직접 자료의 위치를 바꾸면서 정렬시키는 프로그램이다.
리스트 a에서 자료를 하나씩 빼낸 후 다시 result에 넣는 방식인 '쉽게 설명한 선택 정렬 알고리즘'보다 더 효율적으로 정렬할 수 있다.

# 선택 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)

def sel_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        # i번 위치부터 끝까지 자료 값 중 최솟값의 위치를 찾음
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        # 찾은 최솟값을 i번 위치로
        a[i], a[min_idx] = a[min_idx], a[i] # 두 자료 값의 위치를 서로 바꿈

d = [2, 4, 5, 1, 3]
sel_sort(d)
print(d)

알고리즘 분석

자료를 크기 순서로 정렬하려면 반드시 두 수의 크기를 비교해야 한다. 따라서 정렬 알고리즘의 계산 복잡도는 보통 비교 횟수를 기준으로 따진다.
선택 정렬 알고리즘은 이해하기 쉽고 간단하여 많이 이용하지만, 비교 횟수가 입력 크기의 제곱에 비례하는 시간 복잡도가 O($n^2$)인 알고리즘이므로 입력 크기가 커지면 커질수록 정렬하는 데 시간이 굉장히 오래 걸린다.