lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

pythonIntroAlgorithms1Chapter2Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

lesson18Title

lesson19Title

pythonIntroAlgorithms1Chapter1Title

pythonIntroAlgorithms1Chapter3Title

pythonIntroAlgorithms1Chapter4Title

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 현재 요소보다 큰 arr[j]를 다음 위치로 이동
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # 현재 요소를 적절한 위치에 삽입
        arr[j + 1] = key
    return arr


# 예제 사용
example_array = [12, 11, 13, 5, 6]

sorted_array = insertion_sort(example_array)

print("정렬된 배열:", sorted_array) # 정렬된 배열: [5, 6, 11, 12, 13]

# 삽입 정렬 자세히 알아보기

## 1. 반복문 설정

배열의 각 요소에 대해 반복합니다. 첫 번째 요소는 이미 정렬된 것으로 가정합니다.

```python title="반복문 설정"
for i in range(1, len(arr)):
```

<br />

## 2. 현재 요소 선택 및 적절한 위치 탐색

현재 요소를 선택하고, 이전 요소들과 비교하여 적절한 위치를 찾습니다.

```python title="현재 요소 선택 및 적절한 위치 탐색"
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
    arr[j + 1] = arr[j]
    j -= 1
arr[j + 1] = key
```

<br />

## 시간 복잡도

1. `최악의 경우 시간 복잡도`: O(n^2)

   - 최악의 경우는 입력 배열이 역순으로 정렬되어 있을 때 발생합니다. 이 경우, 각 새 요소를 삽입할 때마다 이미 정렬된 배열 부분의 모든 이전 요소들과 비교해야 하므로, n개의 요소에 대해 대략 (nxn)번의 비교가 필요합니다.

2. `최선의 경우 시간 복잡도`: O(n)

   - 배열이 이미 `정렬되어 있는 경우`입니다. 새로운 요소를 삽입할 때마다, 이미 정렬된 부분에서 적절한 위치를 바로 찾을 수 있으므로, 각 요소에 대해 한 번씩만 비교하면 됩니다. 따라서, 배열의 크기만큼, 즉 n번의 비교가 필요합니다.

3. `평균 시간 복잡도`: O(n^2)

   - 일반적인 경우, 즉 배열의 요소들이 무작위로 배치되어 있을 때는 평균적으로 n^2 비례하는 비교가 필요합니다.