Algorithm Guidecomplexity: O(n²)

삽입 정렬 (Insertion Sort)

각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 알고리즘입니다. 데이터가 거의 정렬되어 있을 때 매우 빠른 속도를 자랑합니다.

01삽입 정렬 (Insertion Sort)

알고리즘 작동 원리 탐색

삽입 정렬을 시작합니다. 값을 하나씩 집어 왼쪽의 정렬된 구간에 끼워 넣습니다. 맨 앞 45는 이미 정렬된 것으로 봅니다.

12를 집어 듭니다. 빈자리가 생긴 왼쪽 구간에서 이 값이 들어갈 위치를 찾습니다.

왼쪽의 45는 12보다 큽니다. 자리를 내주도록 한 칸 오른쪽으로 밀어냅니다.

왼쪽에 더 볼 값이 없습니다. 비워진 맨 앞자리에 12를 내려놓습니다.

89를 집어 듭니다. 왼쪽 끝의 45보다 크니 밀어낼 값이 없어 제자리에 그대로 둡니다.

34를 집어 듭니다. 정렬된 12·45·89 사이에서 들어갈 자리를 찾습니다.

89도 45도 34보다 큽니다. 둘 다 한 칸씩 오른쪽으로 밀어냅니다.

12에서 멈춥니다. 34보다 작으니 그 뒤 비워진 자리에 34를 내려놓습니다.

67을 집어 듭니다. 89 하나만 밀어내면 그 자리가 67의 자리입니다.

23을 집어 듭니다. 89·67·45·34를 차례로 밀어내고 12 뒤에 내려놓습니다.

56을 집어 듭니다. 89와 67을 밀어내고 45 뒤에 내려놓습니다.

마지막 10을 집어 듭니다. 가장 작은 값이라 모두 밀어내고 맨 앞에 내려놓습니다.

삽입 정렬이 끝났습니다. 이미 거의 정렬된 배열에서는 밀어낼 값이 적어 특히 빠릅니다.

Live Python

1def insertion_sort(arr):

# i: 1부터 시작

2 for i in range(1, len(arr)):

3 key = arr[i]

4 j = i - 1

5 while j >= 0 and arr[j] > key:

6 arr[j + 1] = arr[j]

7 j -= 1

8 arr[j + 1] = key

9 return arr

1 / 13

02 쉽게 이해하기

For Everyone

🔑핵심 동작

앞쪽을 정렬된 구간으로 두고 다음 값을 그 안의 제자리에 끼워 넣습니다. 거의 정렬된 데이터에서 특히 빠릅니다.

💡쉽게 말하면

앞쪽은 이미 정렬됐다고 보고, 새 값을 적절한 위치에 밀어 넣습니다.

거의 정렬된 데이터에선 매우 빨라요.

📍어디에 쓰나

–소량·거의 정렬된 데이터
–다른 정렬의 마무리 단계

03 파이썬 구현 코드

삽입 정렬 (Insertion Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

04 자주 묻는 질문

FAQ

삽입 정렬 (Insertion Sort)란 무엇인가요?+

각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 알고리즘입니다. 데이터가 거의 정렬되어 있을 때 매우 빠른 속도를 자랑합니다.

삽입 정렬 (Insertion Sort)의 시간복잡도는 어떻게 되나요?+

삽입 정렬 (Insertion Sort)의 시간복잡도는 O(n²) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

삽입 정렬 (Insertion Sort)은(는) 어디에 사용하나요?+

소량·거의 정렬된 데이터, 다른 정렬의 마무리 단계.

삽입 정렬 (Insertion Sort)를 쉽게 비유하면?+

앞쪽을 정렬된 구간으로 두고 다음 값을 그 안의 제자리에 끼워 넣습니다. 거의 정렬된 데이터에서 특히 빠릅니다.

→ 정렬 전체 보기Related

📊버블 정렬 (Bubble Sort)

O(n²)

📊선택 정렬 (Selection Sort)

📊계수 정렬 (Counting Sort)

O(n + k)