CHAPTER 6. 정렬 - 선택 정렬

1. 선택 정렬

현재 위치에 들어갈 값을 찾아서 바꾸는 정렬 알고리즘

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

 

동작 예시

초기 데이터: 7 5 9 0 3 1 6 2 4 8

 

[step 1] 처리되지 않은 데이터(1~10) 중 가장 작은 '0'을 선택해 가장 앞에 있는 '7'과 바꾼다.

→  '0' 정렬 완료

 

[step 2] 정렬된 데이터를 제외하고 처리되지 않은 데이터(2~10) 중 가장 작은 '1'을 선택해 가장 앞에 있는 '5'와 바꾼다.

→  '0', '1' 정렬 완료

 

[step 3] 정렬된 데이터를 제외하고 처리되지 않은 데이터(3~10) 중 가장 작은 '2'를 선택해 가장 앞에 있는 '9'와 바꾼다.

→  '0', '1', '2' 정렬 완료

 

---------- 중략 ----------

 

[step 10] 위의 과정을 총 9번 반복하면 마지막 데이터는 가만히 두어도 이미 정렬된 상태이므로, 이 단계에서 정렬이 완료된다.

→  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 정렬 완료

 

시간 복잡도

• 탐색 범위는 반복할 때마다 1씩 줄어든다.
• 데이터를 앞으로 보내는 과정은 N-1번 반복한다.
• 매번 탐색 범위만큼 데이터를 하나씩 확인하고 비교해서 가장 작은 데이터를 찾는다(선형탐색).
• 선택 정렬은 이중 반복문으로 구현가능하다. = 직관적으로 , 소스 코드의 이중 반복문때문에 O(N²)이 되었다고 이해할 수도 있다.

구현방식에 따라 사소한 오차는 있을 수 있지만 위의 방식대로 한다면, 연산 횟수는 다음과 같다. 이 식은 등차수열 공식에 따라서 다음과 같이 표현할 수 있다.

 

N + ( N - 1 ) + ( N - 2 ) + ··· + 2  

 

이 식은 등차수열 공식에 따라서 다음과 같이 표현할 수 있다.

 

 =  ( N² + N - 2 ) / 2

≒  N × ( N + 1 ) / 2  =  ( N² + N ) / 2

 

빅오 표기법에 따라서 나타내면 계수는 생략되고 가장 차수가 높은 항만 고려한다.

 

Big-O Notation: O(N²)

 

공간 복잡도

• 하나의 배열에서 값을 바꾸는 방식으로 동작하므로 공간 복잡도는 O(1)
• swap할 때 임시변수 하나 정도가 필요 → in-place 정렬

코드

# 선택 정렬 코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
	min_idx = i # 인덱스 선택
    for j in range(i+1, len(array)):
    	if array[min_idx] > array[j]:
        	min_idx = j  min_idx의 값보다 j의 값이 작으면 j로 업데이트
		array[min_idx], array[i] = array[i], array[min_idx] # 안쪽 for문을 돌고나면 가장 작은 원소를 발견, 범위내에 가장 앞의 원소와 swap해준다
        print(array) # 정렬 과정 출력

print(array) # 최종 정렬 결과 출력

---

 

Q. 선택 정렬은 효율적인가?

정렬할 데이터 개수가 100배 늘어나면 이론적으로 수행 시간은 10,000배 늘어난다. 선택 정렬, 퀵 정렬, 기본 정렬 라이브러리의 수행시간을 비교해보면 다음과 같다.(초 단위, 측정 시간은 컴퓨터마다 다를 수 있음)

* 아래 표는 Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz, 2코어 환경에서 측정

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

 

선택 정렬을 이용하면 데이터 개수가 10,000개 이상일 때 정렬 속도가 급격히 느려지는 것을 확인할 수 있다. 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C언어 기반이면 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다. 선택 정렬은 기본 정렬 라이브러리, 다른 알고리즘과 비교했을 때 매우 비효율적이다. 다만, 특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦기때문에 이러한 형태의 소스코드에 익숙해질 필요가 있다. 선택 정렬 소스코드를 자주 작성해볼 것을 권장!

 

 

 

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 그렇다면 다른 접근 방법에는 무엇이 있는지 알아보자

 

CHAPTER 6. 정렬 - 삽입 정렬