[알고리즘] 선택 정렬 (selection sort)

선택 정렬이란?

  - 다음과 같은 순서를 반복하며 정렬하는 알고리즘

      1. 주어진 데이터 중, 최솟값을 찾음

      2. 해당 최솟값을 데이터 맨 앞에 위치한 값과 교체

      3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

 

단계별로 생각하기

  - 예 : data_list = [5, 19, 3, 14]

  - 1차 로직

4개의 값 중에서 가장 작은 값 3을 제일 앞에 있는 5와 교체

인덱스	0	1	2	3
값	5	19	3	14

맨 앞에 위치한 3고정

인덱스	0	1	2	3
값	3	19	5	14

 

  - 2차 로직

맨 앞의 위치를 뺀 나머지 값에서 가장 작은 값 5를 19와 교체

인덱스	0	1	2	3
값	3	19	5	14

앞으로 위치한 5고정

인덱스	0	1	2	3
값	3	5	19	14

 

  - 3차 로직

고정 값을 제외한 나머지 값에서 가장 작은 값 14와 19교체

인덱스	0	1	2	3
값	3	5	19	14

정렬 완료

인덱스	0	1	2	3
값	3	5	14	19

 

알고리즘 구현

def selection_sort(data):
	for stand in range(len(data) - 1):
		lowest = stand
		for index in range(stand + 1, len(data)):
			if data[lowest] > data[index]:
				lowest = index
		data[lowest], data[stand] = data[stand], data[lowest]
	return data
    
data_list = [5, 19, 3, 14]
print(selection_sort(data_list))	# [3, 5, 14, 19]

 

정리

  - 버블 정렬과 성능상 큰 차이가 없다.

  - 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n^2)이다.

  - 이동연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n)이다.