[알고리즘][python] 정렬 알고리즘 - 선택정렬

정렬(sorting) : 데이터를 특정한 기준에 따라 순서대로 나열.

 

선택 정렬 

- 처리되지 않은 데이터 중에서 가장 작은 데이터 선택해 맨 앞 데이터와 바꾸기

 

1. 선택 정렬 작동 원리 ( 예시 )

[64, 25, 12, 22, 11]

 

1단계: 배열 전체에서 가장 작은 값 찾기

 11을 배열의 첫 번째 요소인 64와 교환

 [11, 25, 12, 22, 64]

 

2단계: 두 번째 요소 이후에서 가장 작은 값 찾기

 12를 두 번째 위치에 있는 25와 교환

 [11, 12, 25, 22, 64]

 

3단계: 세 번째 요소 이후에서 가장 작은 값 찾기

 22를 세 번째 위치에 있는 25와 교환

 [11, 12, 22, 25, 64]

 

4단계: 네 번째 요소 이후에서 가장 작은 값 찾기

 이미 자리에 있기 때문에 교환은 필요 없음

 [11, 12, 22, 25, 64]

 

5단계: 마지막 요소는 자동으로 정렬된 상태

 [11, 12, 22, 25, 64]

 

2. 선택 정렬 소스코드 (python)

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i] #위치를 바꾸는 스와프
    return arr

# 예시 실행
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr)  # [11, 12, 22, 25, 64]