[05-01] 정렬 - 선택 정렬

1. 개요 & 알고리즘

정렬을 위해서는 다음과 같은 두 가지 동작이 필요합니다.

첫째 : 크고 작은지에 대한 '판단(decision)'

둘째 : 판단에 따라서 값을 바꾸는 '교환(exchange)'

정렬 알고리즘을 정의하자면 "판단과 교환을 어떻게 적절히 조합하는가에 대한 방법론"이라고 할 수 있습니다. ("C로 배우는 알고리즘")

정렬에서 사용하는 용어를 정리하면 다음과 같습니다.

* 파일(file) : 정렬을 하는 대상

* 레코드(record) : 파일에서 정보의 단위

* 필드(field) : 각 레코드의 정보 단위

* 키(key) : 정렬의 기준

Key를 정렬하는 방법에 따라서 아래와 같이 나눌 수 있습니다.

* 오름차순(ascending order) : 키값을 비교하여 작은 값을 앞에, 큰 값을 뒤에 두는 방법

* 내림차순(descending order) : 오름차순의 반대

정렬 알고리즘의 종류를 다음과 같이 분류할 수 있습니다.

* 간단한 알고리즘 : 선택 정렬, 삽입 정렬, 거품 정렬, 셀 정렬

* 복잡한 알고리즘 : 퀵 정렬, 기수 정렬, 힙 정렬, 병합 정렬

정렬 알고리즘의 "안정성"에 대해서 "C로 배우는 알고리즘"은 다음과 같이 정의하고 있습니다.

"안정성이란 같은 내용을 가지는 키값의 배열이 정렬 후에도 상대적 순서가 그대로 유지되면 그 알고리즘은 안정성이 있다고 하고 유지되지 않는 경우는 안정성이 없다고 한다"

예1 : 사번순으로 정렬한 후 다시 나이 순으로 정렬할 때, 사번의 순서가 유지되면 안정성이 있다고 한다.

예2 : 알파벳을 정렬할 때 같은 알파벳이 중복되어 존재하는 경우, 같은 알파벳의 순서가 정렬 과정에서 기존의 순서를 유지될 때 안정성이 있다고 한다.

"C로 배우는 알고리즘"에 설명된 선택 정렬 알고리즘은 다음과 같습니다.

1. i = 0

2. i가 n-2가 되면 끝낸다

3. 배열의 i항부터 n-1항까지 중 최소값을 찾아서 그 항을 min에 저장한다

4. 배열의 i항과 min항을 교환한다

5. i를 하나 증가시키고 2로 돌아간다

선택 정렬 알고리즘은 앞서 정의한 "안정성"이 없습니다.

정렬 알고리즘의 성능 평가를 위해서는 "이미 정렬된 배열", "난수의 배열", "반쯤 정렬된 배열", "역순의 배열"로 평가하고, 알고리즘간 성능을 비교할 수 있습니다.

2. 동작 코드

Python의 list는 링크 설명과 같이 sort method를 제공하며, 이것을 그대로 사용하면 됩니다. 다만, 알고리즘 이해를 위해서 직접 작성해 보았습니다.

# Select sort algorithm
def select_sort(elements):
    size = len(elements)
    for i in range(size - 1):
        min_index = i
        min_value = elements[i]
        for j in range(i+1, size):
            if min_value > elements[j]:
                min_index = j
                min_value = elements[j]
        elements[min_index] = elements[i]
        elements[i] = min_value

3. 실행 코드

List 'a'를 받아서 선택 정렬을 하는 실행 코드입니다.

if __name__ == '__main__':
    a = ['T', 'O', 'L', 'E', 'A', 'R', 'N', 'S', 'O', 'R', 'T', 'A', 'L', 'G', 'O', 'R', 'I', 'T', 'H', 'M']
    print("Original : ", a)
    select_sort(a)
    print("Sorted : ", a)

안정성 관련해서 원본 데이터를 동일한 'T'의 순서를 확인할 수 있도록 하고 index를 추가하고,

a = ['T1', 'O', 'L', 'E', 'A', 'R', 'N', 'S', 'O', 'R', 'T2', 'A', 'L', 'G', 'O', 'R', 'I', 'T3', 'H', 'M']

select_sort() 함수를 조금 고쳐서 첫번째 값만을 비교하도록 수정하면,

for j in range(i+1, size):
    if min_value[0] > elements[j][0]:

다음과 같은 결과를 얻을 수 있습니다.

Sorted :  ['A', 'A', 'E', 'G', 'H', 'I', 'L', 'L', 'M', 'N', 'O', 'O', 'O', 'R', 'R', 'R', 'S', 'T3', 'T1', 'T2']

즉, 'T'의 순서가 [1, 2, 3]으로 유지되지 않고, [3, 1, 2]로 변경된 것을 알 수 있으며, 이를 통해서 '선택 정렬'은 '안정성'이 없다를 확인할 수 있습니다.

4. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_05/Ch_05_01.py

5. 기타

주로 "C로 배우는 알고리즘"에 적혀 있는 내용을 주고 사용하고, 필요시 인터넷 검색의 결과를 이용하였습니다. 이용한 출처는 밝히는 것을 원칙으로 합니다만, 혹시 실수가 있거나 문제되는 사항이 있다면 알려 주십시오. 수정하도록 하겠습니다.