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

선택 정렬(Selection Sort)은 배열에서 가장 작은 값을 선택하여 순서대로 정렬하는 방법

가장 작은 값을 찾아 앞으로 이동하는 방식으로 동작

 

선택 정렬이 작동하는 방식

1. 배열에서 최소값을 찾음

 - 현재 정렬되지 않은 부분에서 가장 작은 값을 찾아 첫 번째 위치와 교환

2. 두 번째 위치부터 반복

- 정렬되지 않은 부분에서 다시 최소값을 찾아 두번째 위치와 교환

3. 이 과정을 배열이 완전히 정렬될 때까지 반복

 

선택 정렬 동작 예시

정렬되지 않은 리스트: 

[5, 3, 8, 4, 2]

 

첫 번째 패스(가장 작은 값 찾기)

[5, 3, 8, 4, 2] → [2, 3, 8, 4, 5]  (2가 가장 작아서 5와 교환)

 

두 번째 패스(두 번째로 작은 값 찾기)

[2, 3, 8, 4, 5] → [2, 3, 8, 4, 5]  (3이 이미 제자리에 있음)

 

세 번째 패스(세 번째로 작은 값 찾기)

[2, 3, 8, 4, 5] → [2, 3, 4, 8, 5]  (4가 가장 작아서 8과 교환)

 

네 번째 패스(네 번째로 작은 값 찾기)

[2, 3, 4, 8, 5] → [2, 3, 4, 5, 8]  (5가 가장 작아서 8과 교환)

 

최종 정렬된 리스트:

[2 , 3, 4, 5, 8]

 

Phython 코드 구현

1. 기본 선택 정렬

def selection_sort(arr):
	n = len(arr)
    for i in range(n - 1): # 마지막 요소는 자동으로 정렬됨
    	min_idx = i # 최소값의 인덱스를 현재 인덱스로 설정
        for j in range(i + 1, n): # i 이후의 요소에서 최소값 찾기
       		if arr[j] < arr[min_idx]: # 최소값 갱신
            	min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]	# 최소값과 현재 위치 값 교환
    return arr

#테스트
arr = [5, 3, 8, 4, 2]
print(selection_sort(arr)) #[2, 3, 4, 5, 8]

 

2. 최적화된 선택 정렬(불필요한 교환 방지)

기본 선택 정렬에서는 항상 값이 교환되지만, 이미 제자리에 있는 경우 불필요한 교환을 방지

def optimized_selection_sort(arr):
	n = len(arr)
    for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
    	if arr[j] < arr[min_idx]:
        	min_idx = j
    if min_idx != i: # 필요할 때만 교환(불필요한 교환 방지)
    	arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
    
#테스트
arr = [5, 3, 8, 4, 2]
print(optimized_selection_sort(arr)) # [2, 3, 4, 5 , 8]