lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

pythonIntroAlgorithms1Chapter2Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

lesson18Title

lesson19Title

pythonIntroAlgorithms1Chapter1Title

pythonIntroAlgorithms1Chapter3Title

pythonIntroAlgorithms1Chapter4Title

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 현재 위치를 최솟값으로 가정
        min_index = i
        # 나머지 배열에서 최솟값을 찾음
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 찾은 최솟값을 현재 위치로 이동
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


# 예제 사용
example_array = [64, 34, 25, 12, 22, 11, 90]

sorted_array = selection_sort(example_array)

print("정렬된 배열:", sorted_array) # [11, 12, 22, 25, 34, 64, 90]

# 선택 정렬 자세히 알아보기

## 1. 반복문 설정

두 개의 중첩된 반복문을 사용합니다. 외부 반복문은 배열을 통과하는 횟수를 결정하고, 내부 반복문은 최소값을 찾기 위해 배열의 요소를 비교합니다.

```python title="반복문 설정"
for i in range(n):
  for j in range(i + 1, n):
```

<br />

## 2. 최소값 찾기 및 교환

내부 반복문에서, 최소값을 찾아 현재 위치의 값과 교환합니다.

```python title="최소값 찾기 및 교환"
if arr[j] < arr[min_index]:
  min_index = j # 최소값의 인덱스 저장

arr[i], arr[min_index] = arr[min_index], arr[i] # 최소값과 현재 위치의 값 교환
```

<br />

## 선택 정렬 시간 복잡도

1. `최악, 최선, 평균 시간 복잡도 (Worst, Best, and Average-Case Time Complexity)`: 모두 O(n^2)

   - 선택 정렬은 배열의 각 위치에 대해 나머지 전체 배열을 탐색하여 가장 작은(또는 가장 큰) 요소를 찾습니다. 이 과정은 배열의 크기가 n일 때, 첫 번째 요소에 대해 `n-1`번, 두 번째 요소에 대해 `n-2`번 등 총 ((n-1) + (n-2) + ... + 1)번, 즉 `n(n-1)/2` 번의 비교를 필요로 합니다.

   `n(n-1)/2`를 빅오 표기법으로 표기하면, 시간복잡도는 `O(n^2)`가 됩니다.

   - 선택 정렬의 시간 복잡도는 입력 데이터의 정렬 상태에 관계없이 항상 일정합니다. 즉, 이미 정렬된 배열이든, 역순으로 정렬된 배열이든, 무작위로 배치된 배열이든 시간 복잡도는 변하지 않습니다.