선택 정렬

가장 기본적인 정렬 방법 중 하나인 선택 정렬에 대해서 알아보자.

 

선택 정렬 (Selection sort)

기본적인 컨셉은 전체 데이터에서 가장 작은 값을 맨 왼쪽에 넣고, 그다음엔 두 번째로 작은 값을 왼쪽에서 두 번째에 넣는 방식이다. 이런 식으로 반복해주면 점점 정렬이 될 것이고 마지막 데이터는 가만히 두어도 정렬된 상태일 것이다.

stackoverflow.com

 

위의 그림에서는 총 7개의 데이터를 7-1번만큼 반복해서 정렬을 하였다. 데이터가 N개이면 반복 횟수는 N-1번일 것이다.

##메인 함수 부분##
if __name__ == "__main__":
    array = [7,5,9,0,3,1,6,2,4,8]

    for i in range(len(array)):
        min_index = i
        for j in range(i+1, len(array)):
            if array[min_index] > array[j]:
                min_index = j
        array[i] , array[min_index] = array[min_index], array[i] #swap

    print(array)

 

파이썬에서는 데이터의 위치를 바꿀 때 별도의 저장용 변수를 선언하여 값을 저장하여 바꿔줄 필요가 없다.

C언어에서는 아래와 같이 데이터의 위치를 바꿔주어야 한다.

int a = 3;
int b = 5;

int tmp = a;
a = b;
b = tmp;

 

 

시간 복잡도

선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 앞으로 보내야 한다. 그리고 매번 가장 작은 수인지 확인하기 위해서 비교 연산이 필요하다.

처음엔 N개의 데이터를 확인해봐야 하고, 두 번째엔 N-1개의 데이터를, 세 번째엔 N-2개의 데이터를 확인해야 한다. 마지막엔 2개의 데이터를 확인해봐야 한다.

즉 N + (N-1) + (N-2) + ... + 2 인 셈이다.

계산해보면 N X (N+1) / 2 이므로 시간 복잡도는 O(N²)일것이다. 직관적으로는 2중 for문을 사용했기 때문이라고 할 수 있다.

 

지금은 N의 크기가 작아서 수행 시간이 그렇게 느리지 않지만 N의 크기가 100배 늘면, 수행 시간은 제곱으로 늘어난다.

파이썬 3.7의 선택 정렬과 퀵 정렬, 그리고 기본 정렬 라이브러리의 수행 시간을 비교해보자. 아래는 이코테 책에 있는 표를 그대로 가져온 값이다. 

데이터의 개수(N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
N = 100	0.0123초	0.00156초	0.00000753초
N = 1,000	0.354초	0.00343초	0.0000365초
N = 10,000	15.475초	0.0312초	0.000248초

N이 10,000개 이상이면 선택 정렬의 속도가 급격히 느려지는 것을 볼 수 있다. 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C언어 기반이고, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다고 한다.

 

선택 정렬은 다른 정렬 알고리즘에 비해 매우 비효율적이다.

하지만 선택 정렬과 같은 방식으로 특정한 리스트에서 작은 데이터를 찾는 일이 코딩 테스트에서 자주 있으므로 자주 작성해보자.