[Python] 이것이 코딩테스트다 with 파이썬 - 정렬 - 선택 정렬

들어가기 앞서

 

해당 문제 및 해설은 "이것이 코딩 테스트다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다. 

 

 

챕터 순서

 

1. 선택 정렬 알고리즘

2. 삽입 정렬 알고리즘

3. 퀵 정렬 알고리즘

4. 계수 정렬 알고리즘

 

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

---

정렬 알고리즘

 

정렬 이란, 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다.
알고리즘 효율성을 쉽게 이해할 수 있는 정렬을 통하여 코딩 테스트 합격률을 높여보도록 한다. 
정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 정리 해보려고 한다.

 

선택 알고리즘

선택 알고리즘은 데이터가 무작위로 여러 개 있을 때 , 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 

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

 

---

 

선택 정렬 그림 설명

 

 단계 0  초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 '0' 을 선택해 맨 앞에 있는 데이터 '7' 과 바꾼다.

 

  

 단계 1  이제 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1' 을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '5' 와 바꾼다.

 

 

 단계 2  이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '2' 를 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9' 와 바꾼다.

 

  

- - 중략 - - 

 

 단계 8 

 

 

 단계 9  가장 작은 데이터를 앞으로 보내는 과정을 9번 반복한 상태는 다음과 같으며 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 따라서 이 단계에서 정렬을 마칠 수 있다.

 

 

이처럼 선택 정렬을 가장 작은 데이터를 맨 앞으로 보내는 과정을 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]

 

선택 정렬의 시간 복잡도

 

선택 정렬은 N - 1 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

사소한 오차는 있을 수 있지만 위 그림대로 구현 한다면, 연산 횟수는

N + ( N - 1 ) + ( N - 2 ) + 2 로 볼 수 있다.

 

식은 N * ( N + 1 ) / 2 와 같다.

빅오 표기법으로 O(N^2) 이라고 표현 할 수 있다.

 

만약 정렬해야 할 데이터의 개수가 100 배 늘어나면, 이론적으로 수행 시간은 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 초