[Algorithm]삽입 정렬 알고리즘 완벽 가이드: 이해와 파이썬으로 구현

삽입 정렬 알고리즘이란 무엇일까요? 왜 우리는 삽입 정렬을 배워야 할까요? 이번 글에서는 삽입 정렬 알고리즘의 기본 개념부터 구현 방법까지 자세히 알아보겠습니다. 또한, 삽입 정렬과 선택 정렬의 차이점도 살펴보겠습니다.

≣ 목차

• 삽입 정렬 알고리즘의 기본 개념🤔
• 삽입 정렬 알고리즘의단계별 설명🛠️
• 파이썬으로 삽입 정렬 알고리즘 구현💻
• 삽입 정렬의 장단점📊
• 삽입 정렬과 선택 정렬의 차이점🎭

선택 정렬에 대한 자세한 내용은 아래 포스팅을 참고해 주세요😁

[Algorithm]초보자를 위한 파이썬 선택 정렬 알고리즘 완벽 가이드

---

01. 삽입 정렬 알고리즘의 기본 개념🤔

삽입 정렬의 정의

삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 하나로, 데이터가 거의 정렬되어 있을 때 효율적으로 작동합니다. 각 요소를 적절한 위치에 삽입하여 정렬을 완성합니다.

삽입 정렬의 작동 원리

초기 상태:

• 배열의 첫 번째 요소는 이미 정렬된 것으로 간주합니다.
• 두 번째 요소부터 배열의 끝까지 순회하면서 각 요소를 정렬된 부분에 삽입합니다.

정렬 과정:

• 현재 요소를 정렬된 부분의 끝에서부터 비교하여 적절한 위치를 찾습니다.
• 적절한 위치를 찾으면, 해당 위치에 현재 요소를 삽입하고 나머지 요소들을 오른쪽으로 한 칸씩 이동시킵니다.

반복:

• 배열의 모든 요소가 정렬될 때까지 위의 과정을 반복합니다.

예시

다음 예시를 통해 삽입 정렬의 과정을 살펴보겠습니다. 정렬할 배열이 [5, 2, 9, 1, 5, 6]이라고 가정합니다.

초기 상태: [5, 2, 9, 1, 5, 6]

• 첫 번째 요소 5는 이미 정렬된 상태로 간주합니다.

2 삽입:

• 두 번째 요소 2를 정렬된 부분(첫 번째 요소 5)과 비교합니다.
• 2는 5보다 작으므로 5 앞에 삽입합니다.
• 결과: [2, 5, 9, 1, 5, 6]

9 삽입:

• 세 번째 요소 9를 정렬된 부분(2, 5)과 비교합니다.
• 9는 5보다 크므로 제자리에 위치합니다.
• 결과: [2, 5, 9, 1, 5, 6]

1 삽입:

• 네 번째 요소 1을 정렬된 부분(2, 5, 9)과 비교합니다.
• 1은 2보다 작으므로 2 앞에 삽입합니다.
• 결과: [1, 2, 5, 9, 5, 6]

5 삽입:

• 다섯 번째 요소 5를 정렬된 부분(1, 2, 5, 9)과 비교합니다.
• 5는 9보다 작고 5보다 크지 않으므로 두 번째 5의 앞에 삽입합니다.
• 결과: [1, 2, 5, 5, 9, 6]

6 삽입:

• 여섯 번째 요소 6을 정렬된 부분(1, 2, 5, 5, 9)과 비교합니다.
• 6은 9보다 작고 5보다 크므로 9 앞에 삽입합니다.
• 결과: [1, 2, 5, 5, 6, 9]

이 과정을 통해 배열이 완전히 정렬됩니다.

시간 복잡도

• 최선의 경우: O(n)
• 평균의 경우: O(n²)
• 최악의 경우: O(n²)

공간 복잡도

• O(1): 추가적인 메모리를 거의 사용하지 않습니다.

---

02. 삽입 정렬 알고리즘의 단계별 설명🛠️

초기 상태 설명

정렬되지 않은 배열이 주어집니다. 예: [12, 11, 13, 5, 6]

각 단계별 요소 삽입 과정 설명

1. 두 번째 요소 11을 첫 번째 요소 12와 비교하여 12 앞에 삽입합니다. [11, 12, 13, 5, 6]
2. 세 번째 요소 13은 이미 정렬된 상태입니다. [11, 12, 13, 5, 6]
3. 네 번째 요소 5를 첫 번째 요소 11과 비교하여 적절한 위치에 삽입합니다. [5, 11, 12, 13, 6]
4. 마지막 요소 6을 적절한 위치에 삽입합니다. [5, 6, 11, 12, 13]

완료 상태 설명

모든 요소가 정렬되어 최종적으로 [5, 6, 11, 12, 13]이 됩니다.

---

03. 파이썬으로 삽입 정렬 알고리즘 구현💻

def insertion_sort(arr):  # 배열을 인수로 받아 삽입 정렬을 수행하는 함수 정의
    for i in range(1, len(arr)):  # 배열의 두 번째 요소부터 마지막 요소까지 반복
        key = arr[i]  # 현재 삽입할 요소를 key에 저장
        j = i - 1  # key의 이전 요소를 가리키는 인덱스 j를 설정
        # key가 정렬된 부분에서 적절한 위치를 찾을 때까지 비교하고 이동
        while j >= 0 and key < arr[j]:  # key보다 큰 요소들을 오른쪽으로 이동
            arr[j + 1] = arr[j]  # 요소를 오른쪽으로 이동
            j -= 1  # 인덱스를 한 칸 왼쪽으로 이동
        # 적절한 위치에 key 삽입
        arr[j + 1] = key  # key를 올바른 위치에 삽입

# 사용 예제
arr = [5, 2, 9, 1, 5, 6]  # 정렬할 배열 정의
insertion_sort(arr)  # 삽입 정렬 함수 호출
print(arr)  # 정렬된 배열 출력: [1, 2, 5, 5, 6, 9]

구현 코드 설명

1. for 루프는 두 번째 요소부터 시작하여 배열의 모든 요소를 반복합니다.
2. while 루프는 현재 요소를 앞의 요소들과 비교하여 올바른 위치를 찾습니다.
3. 적절한 위치에 도달하면 요소를 삽입합니다.

---

04. 삽입 정렬의 장단점📊

삽입 정렬(Insertion Sort)은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘의 장단점을 이해하면 어떤 상황에서 사용하기 적합한지 판단할 수 있습니다.

장점

1. 간단한 구현:
   삽입 정렬은 알고리즘이 직관적이며, 코드가 간단해서 이해하고 구현하기 쉽습니다.
2. 적은 데이터 이동:
   이미 정렬된 배열에 새로운 요소를 삽입할 때 최소한의 이동만 필요합니다.
3. 적은 메모리 사용:
   삽입 정렬은 제자리 정렬(in-place sort) 알고리즘으로, 추가적인 메모리를 거의 사용하지 않습니다.
4. 작은 배열에서 효율적:
   데이터의 개수가 적을 때 매우 빠르게 동작합니다. 일반적으로 데이터의 개수가 10개 이하일 때는 삽입 정렬이 매우 효율적입니다.
5. 부분적으로 정렬된 데이터에서 효율적:
   이미 부분적으로 정렬된 배열에 대해 매우 효율적으로 동작합니다. 최선의 경우 시간 복잡도는 O(n)입니다.
6. 안정성:
   삽입 정렬은 안정 정렬(stable sort)입니다. 즉, 동일한 키를 가진 요소들의 상대적인 순서가 유지됩니다.

단점

1. 비효율적인 시간 복잡도:
   평균 및 최악의 경우 시간 복잡도는 O(n²)입니다. 따라서 데이터의 개수가 많을 경우 비효율적입니다.
2. 큰 배열에서 비효율적:
   데이터의 개수가 많은 경우 성능이 급격히 저하됩니다. 이 때문에 큰 배열을 정렬할 때는 더 효율적인 알고리즘(예: 퀵 정렬, 병합 정렬 등)을 사용하는 것이 좋습니다.
3. 비교와 이동이 많음:
   정렬되지 않은 데이터를 삽입할 때 비교와 데이터 이동이 많이 발생할 수 있습니다.

결론

삽입 정렬은 간단하고 효율적인 경우가 많지만, 데이터가 많거나 대부분 정렬되지 않은 경우에는 다른 정렬 알고리즘을 사용하는 것이 좋습니다. 적은 양의 데이터나 이미 부분적으로 정렬된 데이터를 다룰 때는 삽입 정렬이 매우 효율적일 수 있습니다.

---

05. 삽입 정렬과 선택 정렬의 차이점🎭

삽입 정렬(Insertion Sort)과 선택 정렬(Selection Sort)은 둘 다 비교 기반의 정렬 알고리즘으로, 간단한 구현과 이해하기 쉬운 알고리즘입니다. 하지만 두 알고리즘은 데이터 처리 방식과 효율성에서 차이가 있습니다.

삽입 정렬(Insertion Sort)

작동 원리:

• 배열을 왼쪽에서 오른쪽으로 순회하면서 각 요소를 이미 정렬된 부분에 적절한 위치에 삽입합니다.
• 새로운 요소를 삽입할 때마다 이전 요소들과 비교하여 적절한 위치를 찾아 삽입합니다.

시간 복잡도:

• 최선의 경우: O(n) (데이터가 이미 정렬된 경우)
• 평균 및 최악의 경우: O(n²) (데이터가 정렬되지 않은 경우)

공간 복잡도:

• O(1) (제자리 정렬, 추가적인 메모리 사용이 거의 없음)

특징:

• 안정 정렬: 동일한 값의 요소들이 정렬 후에도 원래의 상대적 순서를 유지합니다.
• 온라인 정렬: 새로운 요소가 추가될 때마다 정렬된 상태를 유지할 수 있습니다.

적용 사례:

• 작은 데이터셋
• 이미 대부분 정렬된 데이터
• 실시간으로 데이터가 추가되는 경우

선택 정렬(Selection Sort)

작동 원리:

• 배열을 순차적으로 순회하면서, 각 위치에 대해 해당 위치부터 배열 끝까지의 최솟값을 찾아 해당 위치와 교환합니다.
• 처음부터 끝까지 순회하면서, 현재 위치에 가장 작은 요소를 선택하여 교환하는 과정을 반복합니다.

시간 복잡도:

• 최선, 평균, 최악의 경우 모두 O(n²)

공간 복잡도:

• O(1) (제자리 정렬, 추가적인 메모리 사용이 거의 없음)

특징:

• 비안정 정렬: 동일한 값의 요소들이 정렬 후에 원래의 상대적 순서를 유지하지 않을 수 있습니다.
• 전체 배열을 순회하면서 최솟값을 찾기 때문에, 데이터의 분포에 상관없이 일정한 시간 복잡도를 가집니다.

적용 사례:

• 작은 데이터셋
• 메모리 사용이 중요한 경우

주요 차이점 요약

알고리즘의 작동 방식:

• 삽입 정렬: 현재 요소를 정렬된 부분에 삽입
• 선택 정렬: 현재 위치부터 끝까지 최솟값을 찾아 교환

안정성:

• 삽입 정렬: 안정 정렬
• 선택 정렬: 비안정 정렬

최선의 경우 시간 복잡도:

• 삽입 정렬: O(n) (이미 정렬된 경우)
• 선택 정렬: O(n²) (항상 동일)