[알고리즘] 단순 선택 정렬

선택 정렬이란?

- 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

- 원솟값을 비교하는 횟수: (n² - n) / 2번

- 시간복잡도 측면에서 퀵 정렬과 같은 다른 정렬방법이나 파이썬 내장 라이브러리를 사용한 정렬 방법보다 비효율적

 

선택 정렬의 수행 과정

1. 선택 정렬은 첫 번째 원소를 두 번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 원소를 찾아 첫 번째에 놓음 2. 두 번째 원소를 세 번째 원소부터 마지막 원소까지와 차례대로 비교, 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복

선택 정렬은 위와 같은 과정으로 수행된다.

다시 한 번 간단히 정리하면, 선택 정렬은 아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택, 아직 정렬하지 않은 부분의 맨 앞 원소와 교환하는 작업을 반복하는 정렬 방법이다.

 

이 작업을 반복하게 되면 다음과 같이 정렬이 완료된다.

위 과정들에서 공통되는 부분을 정리하면 다음과 같다.

1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택 2. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환

이를 코드로 표현하면 다음과 같아지게 된다.

# 단순 선택 정렬 알고리즘 구현하기

from typing import MutableSequence

def selection_sort(a: MutableSequence) -> None:
    """단순 선택 정렬"""
    n = len(a) # 배열의 길이 담아주기
    for i in range(n - 1): # 맨 뒤 원소는 자동으로 가장 큰 값이 남게 되기때문에 n - 1까지
        min = i # 매번 i를 min에 담아줌
        for j in range(i + 1, n): # i는 첫번째부터, j는 두번째부터 비교
            if a[j] < a[min]: # j번째 원소보다 min이 크다면
                min = j # j가 가장 작은 값이므로 min에 넣어줌
        a[i], a[min] = a[min], a[i] # 위치를 교환

if __name__ == "__main__":
    print("선택 정렬을 수행합니다.")
    num = int(input("원소 수를 입력하세요.: "))
    x = [None] * num # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f"x[{i}]: "))

    selection_sort(x) # 배열 x를 선택 정렬

    print("오름차순으로 정렬했습니다.")
    for i in range(num):
        print(f"x[{i}] = {x[i]}")

 

실행 결과

선택 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 8
x[3]: 3
x[4]: 1
x[5]: 9
x[6]: 7
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

Process finished with exit code 0

 

하지만, 단순 선택 정렬 알고리즘은 안정적이지 않은 정렬을 한다. 

예를 들어 값이 같은 두 원소가 있을 때 정렬을 수행하는 과정에서 중복된 값을 인식하지 못해 정렬이 필요 없는 데이터의 위치를 바꾸게 되는 경우가 있기 때문이다. 이유는 서로 이웃하지 않는 떨어져 있는 원소를 교환하기 때문이다.