삽입 정렬

6.1 삽입 정렬 정의

삽입 정렬 (Insertion Sort)은 한 번에 한 요소씩 정렬된 배열(또는 리스트)을 빌드하는 정렬 알고리즘이야. 정렬되지 않은 부분에서 각 요소를 가져와 정렬된 부분의 올바른 위치에 삽입하는 방식이지.

작동 원리:

1. 배열의 두 번째 요소부터 시작해 (첫 번째 요소는 이미 정렬된 것으로 간주함).
2. 현재 요소를 이전 요소들과 비교하면서 올바른 위치를 찾을 때까지 왼쪽으로 이동시킴.
3. 배열의 모든 요소에 대해 이 과정을 반복하여, 새 요소를 정렬된 부분의 올바른 위치에 삽입함.

삽입 정렬의 시간 및 공간 복잡도

시간 복잡도:

• 최악의 경우: O(n^2) — 요소들이 처음에 역순으로 배열된 경우 발생.
• 평균 경우: O(n^2) — 요소들이 무작위로 배열된 경우 발생.
• 최선의 경우: O(n) — 요소들이 이미 정렬되어 있는 경우 발생.

공간 복잡도:

O(1) — 알고리즘이 일정한 수의 추가 메모리만 사용하기 때문이지 (임시 값을 저장할 몇몇 변수들만 필요함).

6.2 알고리즘 작동 분석

알고리즘이 진행되는 단계에서의 상황:

• 현재 i 인덱스에 있는 요소가 있음.
• 이 요소의 왼쪽에 있는 모든 요소는 이미 작은 것에서 큰 것으로 정렬되어 있음.
• 현재 요소를 정렬된 부분에 삽입하여 순서가 깨지지 않도록 시도함.

정렬된 부분에 요소를 삽입하려는 시도는 다음과 같음:

1. 변수 j는 i - 1에서 0까지의 값을 순환함.
2. 현재 (i 번째) 요소가 j 번째 요소보다 작으면, j 번째 요소의 값을 오른쪽으로 한 칸 이동시킴.

예시: 현재 상황:

• 녹색은 이미 정렬된 요소들을 나타냄.
• 핑크는 아직 정렬되지 않은 요소들을 나타냄.
• 현재 요소 인덱스 5는 갈색으로 표시됨.

현재 요소를 정렬된 부분의 올바른 위치에 찾으려 시도합니다.

단계 1 — 현재 요소의 값을 변수 key에 저장합니다.

단계 2 — 요소 No4가 key 보다 큽니까? (10은 5보다 큽니까?) 그렇다면 요소 No4를 오른쪽으로 이동:

단계 3 — 요소 No3가 key 보다 큽니까? (8은 5보다 큽니까?) 그렇다면 요소 No3를 오른쪽으로 이동:

단계 4 — 요소 No2가 key 보다 큽니까? (6은 5보다 큽니까?) 그렇다면 요소 No2를 오른쪽으로 이동:

단계 5 — 요소 No1가 key 보다 큽니까? (4은 5보다 큽니까?) 아니요. 그렇다면 요소 No2가 있던 자리에 key를 저장합니다.

우리는 요소 No5를 적절한 위치에 삽입한 후, 다음 No6 요소로 이동하여 정렬된 부분에서 올바른 자리를 찾습니다.

그 다음 7번째 요소:

그 다음 8번째 요소:

6.3 삽입 정렬 알고리즘 구현

다음은 Python으로 구현한 알고리즘이야:

def insertion_sort(arr):
    # 두 번째 요소부터 배열의 모든 요소를 반복
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 키보다 큰 arr[0..i - 1]의 요소들을 한 위치씩 앞으로 이동
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # 키를 올바른 위치에 삽입
    return arr  # 정렬된 배열 반환
        
# 사용 예시:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("정렬된 배열:", sorted_arr)
# 출력: 정렬된 배열: [5, 6, 11, 12, 13]

설명:

• 현재 요소를 key에 저장
• 배열의 정렬된 부분의 모든 요소를 오른쪽으로 이동
• 우리의 요소를 적절한 위치에 삽입

알고리즘 작동 예시

배열 예시: [12, 11, 13, 5, 6]

1. 첫 번째 패스 (i = 1):

• 11과 12를 비교하고, 12를 오른쪽으로 이동.
• 배열: [11, 12, 13, 5, 6]

2. 두 번째 패스 (i = 2):

• 13은 이미 제자리에 있음.
• 배열: [11, 12, 13, 5, 6]

3. 세 번째 패스 (i = 3):

• 5를 13, 12, 11과 비교하고, 모두 오른쪽으로 이동.
• 배열: [5, 11, 12, 13, 6]

4. 네 번째 패스 (i = 4):

• 6을 13, 12, 11과 비교하고, 모두 오른쪽으로 이동.
• 배열: [5, 6, 11, 12, 13]

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