[알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python

이 글은 '이것이 코딩테스트다(나동빈 저)'를 공부하면서 정리한 글입니다.

1. 정렬(Sorting)이란?

- 정렬은 '특정한 기준에 따라서 데이터를 순서대로 나열하는 것'을 말합니다. 흔히 우리가 알고있는 '오름차순', '내림차순'이 이에 해당됩니다.

- 정렬 알고리즘은 단순히 데이터를 정렬하는 것을 넘어 '이진탐색(Binary Search)'를 가능하게 하는 일명 전처리 단계와 같습니다.

- 정렬 알고리즘에는 많은 종류가 존재하지만, 코딩테스트에 많이 사용되는 대표 4인방(선택 정렬, 삽입 정렬, 퀵 정렬, 계수정렬)만 다루도록 하겠습니다. 

 

2. 선택 정렬(Selection Sort)

2.1 선택 정렬의 원리

- 선택 정렬(Selection Sort)에서는, 데이터가 무작위로 있을 때에 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복합니다. 이것은 가장 원시적인 방법으로 "늘 가장 작은 것을 선택한다"는 의미에서 선택 정렬(Selection Sort) 알고리즘이라고 합니다.   

 

2.2 선택 정렬 코드

출처: [위키백과] 선택정렬(Selection Sort)

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]

 

[이해를 더하기 위한 설명]

<한줄 설명> 첫번째 자리부터 마지막 자리까지 차례 차례 가장 작은 값을 고정해 나간다" 1) 가장 작은 값부터 첫번째 자리에 채워 간다고 했는데, 가장 작은 값은 어떻게 찾을까요?    - 가장 작은 값은 자신의 위치(k) 다음부터 끝까지(k+1~ 끝) 하나씩 비교해서,      작은 값이 존재하면 자신과 자리를 바꿉니다.    - 이 과정을 거치면 자신의 위치(k) 이후, 즉 (k+1)이후로는 k보다 더 큰 값이 존재하지 않습니다!       이미 작은 값은 바꿔버렸기 때문이죠. 2) 첫번째 자리부터 고정해나가기 때문에, 내가 i번째 자리를 고정했다면 그 다음은 i+1자리만 보면 됩니다.

<수도코드> for i = 0 to n:     a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.     a[i]와 a[j]의 값을 서로 맞바꾼다.

 

2.3 시간복잡도 

2.3.1 선택 정렬의 시간복잡도

- 선택정렬은 N-1번 만큼 가장 작은 수를 찾아서 앞으로 보내야 하며, 매번 가장 작은 수를 찾기위해서는 비교연산이 필요합니다. 

- 위의 코드와 같이 구현했을 경우, N + (N-1) + (N-2) + (N-3) + ... + 2로 볼 수있습니다.

  => 이를 근사하여 "N(N+1)/2 = (N²+N)/2"로 표현할 수 있는데, 이를 간단히 O(N²)로 표현합니다. 

[위키백과] 선택정렬(Selection Sort)

 

2.3.2 다른 정렬과 시간복잡도 비교

다른 정렬 이름	설명
버블 정렬(Bubble Sort)	- 시간 복잡도 Θ(n²)인 정렬 알고리즘 중에서 버블 정렬보다 선택 정렬이 항상 우수
삽입 정렬(Insertion Sort)	- 삽입 정렬은 k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다는 점에서 유사 - 하지만 선택 정렬은 k+1 번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만, 삽입 정렬은 k+1 번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있습니다.
합병 정렬(Merge Sort)	- 선택 정렬은 합병 정렬과 같은 분할 정복 알고리즘을 사용하지만 일반적으로 큰 배열보다 작은 배열(요소 10~20개 미만)에서 더 빠름 - 충분히 작은 하위 목록에만 삽입 정렬 혹은 선택 정렬을 이용해서 최적화하는 것이 좋음

[위키백과] 선택 정렬(https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC)

 

- 선택 정렬의 복잡도(O(N²))는 다른 정렬과 비교했을때, 효율적이지 않습니다. 특히 데이터의 개수(N)이 많을 경우 연산 속도가 매우 저하됩니다. 다른 접근 방법에 대해서 하나씩 알아봅시다.

- 다음 글에서는 삽입정렬(Insertion Sort)에 대해서 알아보도록 하겠습니다. 

2021.07.10 - [알고리즘(Algorithm)] - [알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python

[알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python

 

<참고> '이것이 코딩 테스트다 with 파이썬'

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077 

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고