Algorithm Guidecomplexity: O(n²)

선택 정렬 (Selection Sort)

배열에서 가장 작은(혹은 가장 큰) 요소를 반복적으로 찾아 맨 앞의 요소와 교체하는 방식으로 정렬을 수행하는 직관적인 제자리 정렬 알고리즘입니다.

01선택 정렬 (Selection Sort)

알고리즘 작동 원리 탐색

선택 정렬을 시작합니다. 아직 정리되지 않은 구간에서 가장 작은 값을 찾아 맨 앞으로 보내는 일을 반복합니다.

첫 자리에 놓을 값을 고릅니다. 일단 맨 앞의 45를 후보로 두고 오른쪽 전체를 훑습니다.

훑는 동안 12가, 다시 10이 후보를 갈아치웁니다. 전체에서 가장 작은 값은 맨 끝의 10입니다.

찾은 10을 첫 자리로 보냅니다. 그 자리에 있던 45는 10이 있던 끝자리로 갑니다.

다음은 두 번째 자리입니다. 남은 값 중 가장 작은 12가 이미 그 자리에 있어 옮길 것이 없습니다.

세 번째 자리를 채울 차례입니다. 남은 89·34·67·23·56·45 중에서 가장 작은 값을 찾습니다.

가장 작은 값은 23입니다. 지금 그 자리를 차지한 89와 맞바꿀 준비를 합니다.

23을 세 번째 자리로 보냅니다. 89는 23이 있던 자리로 물러납니다.

네 번째 자리는 34입니다. 남은 값 중 가장 작아 이번에도 교환은 없습니다.

다섯 번째 자리에는 남은 값 중 가장 작은 45가 옵니다. 그 자리의 67과 맞바꿉니다.

왼쪽 다섯 자리가 확정됐습니다. 한 자리를 채울 때마다 정렬된 구간이 한 칸씩 자랍니다.

여섯 번째 자리에는 56이 옵니다. 그 자리를 차지한 89와 맞바꿉니다.

남은 89와 67의 순서만 바로잡으면 끝입니다. 둘을 맞바꿉니다.

선택 정렬이 끝났습니다. 교환은 자리마다 한 번뿐이지만, 최솟값을 찾느라 매번 남은 구간 전체를 훑습니다.

Live Python

1def selection_sort(arr):

# n: 8

2 n = len(arr)

3 for i in range(n):

4 min_idx = i

5 for j in range(i + 1, n):

6 if arr[j] < arr[min_idx]:

7 min_idx = j

8 arr[i], arr[min_idx] = arr[min_idx], arr[i]

9 return arr

1 / 14

02 쉽게 이해하기

For Everyone

🔑핵심 동작

남은 구간에서 가장 작은 값을 찾아 맨 앞과 바꿉니다. 교환 횟수가 n-1 로 적습니다.

💡쉽게 말하면

매번 최솟값을 찾아 앞에서부터 채웁니다.

교환 횟수는 적지만 비교는 항상 O(n²)이에요.

📍어디에 쓰나

–교환 비용이 클 때
–정렬 개념 학습

03 파이썬 구현 코드

선택 정렬 (Selection Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr