Python 70 - 정렬 _ 기준에 따라 데이터를 정렬 (선택 정렬)

선택 정렬

컴퓨터가 데이터를 정렬할 때 어떻게 할지 한번 생각해보자.

데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 잇는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번쨰 데이터와 바꾸는 과정을 반복하면 어떨까?

이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort) 알고리즘 이라고 한다. 

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

이해를 돕기 위해 에제를 통해 자세한 동작 원리를 확인하겠다.

 

정렬 알고리즘에서는 흔히 데이터의 개수를 N 이라고 표현한다. 다음 예제에서는 N=10인 경우를 가정한다. 또한 다음의 그림에서 회색 카드는 '현재 정렬되지 않은 데이터 중에서 가장 작은 데이터'를 의미하며, 하늘색 카드는 '이미 정렬된 데이터'를 의미한다.

선택 정렬 그림 설명

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1 번 반복하면 정렬이 완료되는 것 을 알 수 있다.

파이썬으로 작성한 소스코드는 다음과 같다.

선택 정렬 소스 코드

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] # 스와프
    
print(array)

출력결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

다만, 이 코드는 스와프(Swap)에 대해서 모른다면 이해하기 어려운 부분이 있다. 스와프란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미한다. 파이썬에서는 다음처럼 간단히 리스트 내 두원소의 위치를 변경할 수 있다. 하지만 다른 대부분의 프로그래밍 언어에서는 명시적으로 임시 저장용 변수를 만들어 두 원소의 값을 변경해야 한다.

파이썬 스와프(Swap) 소스코드

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

출력결과
[5, 3]

다른 언어에서도 별도의 스와프 함수가 있지만 파이썬만큼 간편하지는 않다. 다음은 C언어에서 표준 라이브러리를 사용하지 않고 2개의 변수 a와 b의 값을 서로 교체하도록 작성한 코드이다. 다음의 코드는 비교용으로 작성된 코드로, 완전한 C 언어 코드 형태가 아니다.

C 언어로 구현한 스와프 예제

int a = 3;
int b = 5;

// 스와프 진행
int temp = a;
a = b;
b = temp;

선택 정렬의 시간 복잡도

그렇다면 선택 정렬의 시간 복잡도를 계산해보자. 선택 정렬은 N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 구현 방식에 따라서 사소한 오차는 있을 수 있지만 앞쪽의 그림대로 구현했을 때 연산횟수는 N + (N - 1) + ( N - 2) + ... + 2 로 볼 수 있다. 따라서 근사치로 N x (N + 1) / 2번의 연산을 수행한다고 가정하자. 이는 (N² + N) /2 로 표현할 수 있는데, 빅오 표기법으로 간단히 O(N²) 이라고 표현할 수 있다.

 

이전에 반복문이 얼마나 중첩되었는지를 기준으로 간단히 시간 복잡도를 판단할 수 있다고 하였다. 선택 정렬의 시간 복잡도는O(N²)이다. 직관적으로 이해하자면, 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이라고 이해할 수 있다.

 

만약 정렬해야 할 데이터의 개수가 100배 늘어나면, 이론적으로 수행 시간은 10,000배로 늘어난다.

그렇다면 이러한 시간 복잡도를 가지는 선택 정렬이 얼마나 효율적일까?

한 번 알고리즘의 수행 시간을 측정해보자.

다음 표는 파이썬3.7의 선택 정렬 알고리즘과 이후에 다룰 퀵 정렬 알고리즘, 그리고 기본 정렬 라이브러리의 수행 시간을 비교한 결과이다. 측정 시간은 각각의 컴퓨터마다 다를 수 있다. 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려지는 것을 확인할 수 있다. 또한 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C언어 기반이며, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다.

데이터의 개수(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 초

선택 정렬은 기본 정렬 라이브러리를 포함해 뒤에서 다룰 알고리즘과 비교했을 때 매우 비효율적이다.

다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다. 그러므로 선택 정렬 소스코드를 자주 작성해볼 것을 권한다.

 

 

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding