선택 정렬

7.1 선택 정렬의 정의

선택 정렬 (Selection Sort)은 정렬되지 않은 배열에서 가장 작은 요소를 찾아 해당 부분의 첫 번째 요소와 위치를 교환하는 알고리즘이야. 이 과정을 반복하면서 배열 전체를 정렬해.

작동 원리:

1. 배열의 첫 번째 요소부터 시작해.
2. 남아 있는 정렬되지 않은 부분에서 가장 작은 요소를 찾아.
3. 가장 작은 요소와 해당 부분의 첫 번째 요소를 교환해.
4. 전체 배열이 정렬될 때까지 다음 요소에 대해 이 과정을 반복해.

단계별 과정

1. 배열에서 가장 작은 요소를 찾아 첫 번째 요소와 위치를 교환해.
2. 나머지 배열에 대해 이 과정을 반복해 (두 번째 요소부터 시작).
3. 전체 배열이 정렬될 때까지 이 과정을 이어가.

선택 정렬의 시간 및 공간 복잡도

시간 복잡도:

• 최악의 경우: O(n^2) — 요소들이 처음부터 역순이거나 무작위로 정렬된 경우 발생해.
• 평균 경우: O(n^2) — 요소들이 무작위로 배치된 경우 발생해.
• 최선의 경우: O(n^2) — 배열이 이미 정렬되어 있어도 동일한 비교를 수행해.

공간 복잡도:

O(1) — 알고리즘이 추가적인 메모리를 거의 사용하지 않아 (단지 임시 값을 저장하기 위한 몇 개의 변수만 사용해).

7.2 선택 정렬 알고리즘의 구현

알고리즘 구현은 매우 간단해:

1단계: 모든 요소 중에서 최소값을 찾아 첫 번째 요소와 위치를 교환해.

2단계: 첫 번째 요소를 제외한 모든 요소 중에서 최소값을 찾아 두 번째 요소와 위치를 교환해.

3단계: 첫 번째와 두 번째 요소를 제외한 모든 요소 중에서 최소값을 찾아 세 번째 요소와 위치를 교환해.

Python으로 구현하기:

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  # 정렬된 배열 반환하기

# 사용 예:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("정렬된 배열:", sorted_arr)
# 출력: 정렬된 배열: [11, 12, 22, 25, 64]

알고리즘 작동 예:

1. 첫 번째 순회 (i = 0):
   1. 정렬되지 않은 부분 [64, 25, 12, 22, 11]에서 최소 요소 (11)를 찾아.
   2. 11과 64를 교환해.
   3. 배열: [11, 25, 12, 22, 64]
2. 두 번째 순회 (i = 1):
   1. 정렬되지 않은 부분 [25, 12, 22, 64]에서 최소 요소 (12)를 찾아.
   2. 12와 25를 교환해.
   3. 배열: [11, 12, 25, 22, 64]
3. 세 번째 순회 (i = 2):
   1. 정렬되지 않은 부분 [25, 22, 64]에서 최소 요소 (22)를 찾아.
   2. 22와 25를 교환해.
   3. 배열: [11, 12, 22, 25, 64]
4. 네 번째 순회 (i = 3):
   1. 정렬되지 않은 부분 [25, 64]에서 최소 요소 (25)를 찾아.
   2. 25는 이미 제자리에 있어 교환 필요 없음.
   3. 배열: [11, 12, 22, 25, 64]

모든 요소가 정렬되어 알고리즘이 종료돼.