제로베이스 데이터사이언스 스쿨 - Part 05. 자료구조&알고리즘 with Python -26

Chapter 03. 알고리즘

삽입 정렬(Insertion Sort) 정리

1. 개념 이해

삽입 정렬은 데이터를 하나씩 확인하면서 이미 정렬된 부분에 새로운 값을 알맞은 위치에 끼워 넣는 방식의 정렬 알고리즘이다. 카드 게임에서 손에 든 카드를 정렬하는 과정과 매우 유사한 구조를 가진다.

리스트의 두 번째 원소부터 시작하여, 현재 값이 앞쪽의 정렬된 데이터들과 비교되며 들어갈 위치를 찾는다. 이때 현재 값보다 큰 값들은 한 칸씩 뒤로 밀리고, 빈 자리에 현재 값이 삽입된다.

---

2. 동작 방식

삽입 정렬의 흐름은 다음과 같다.

1. 두 번째 데이터부터 시작한다.
2. 현재 값을 임시 변수에 저장한다.
3. 앞쪽에 있는 값들과 비교하면서, 현재 값보다 큰 요소들은 오른쪽으로 이동시킨다.
4. 비교가 끝나면 적절한 위치에 현재 값을 삽입한다.
5. 리스트의 끝까지 이 과정을 반복한다.

이미 앞부분이 정렬되어 있다는 가정을 기반으로 하기 때문에, 정렬이 어느 정도 되어 있는 데이터에서는 효율적으로 동작한다.

---

3. 시간 복잡도 특징

• 최악의 경우(역순 정렬): O(n²)
• 평균 시간 복잡도: O(n²)
• 최선의 경우(이미 정렬된 상태): O(n)

데이터의 상태에 따라 성능 차이가 크다는 점이 삽입 정렬의 중요한 특징이다.

---

4. 실습 문제 요약

실습에서는 다음과 같은 요구 사항을 만족하는 프로그램을 구현한다.

• 1부터 1000 사이의 난수 100개를 생성한다.
• 생성된 난수를 삽입 정렬 알고리즘을 이용해 오름차순 또는 내림차순으로 정렬한다.
• 정렬된 결과를 기반으로 최솟값과 최댓값을 반환하는 함수를 구현한다.

이 실습을 통해 단순히 정렬 결과를 얻는 것이 아니라, 정렬 로직 내부에서 데이터가 어떻게 이동하는지를 직접 확인할 수 있다.

---

5. 코드 예시 (삽입 정렬)

import random

numbers = [random.randint(1, 1000) for _ in range(100)]

def insertion_sort(data, reverse=False):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and ((data[j] > key and not reverse) or (data[j] < key and reverse)):
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

sorted_asc = insertion_sort(numbers.copy())
sorted_desc = insertion_sort(numbers.copy(), reverse=True)

print('Min:', min(sorted_asc))
print('Max:', max(sorted_asc))

 

 

 

* 이 글은 제로베이스 데이터사이언스 파트타임 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.

---

 

💡 생각 정리

삽입 정렬은 구현 자체는 단순하지만, 내부 동작을 정확히 이해하지 않으면 단순한 반복문 정렬처럼 보이기 쉽다. 실습을 통해 값을 하나 옮길 때마다 비교와 이동이 어떻게 일어나는지 직접 따라가 보니, 왜 시간 복잡도가 O(n²)이 되는지 자연스럽게 이해할 수 있었다. 특히 데이터가 이미 어느 정도 정렬되어 있을 때는 불필요한 비교가 줄어들어 효율적으로 동작한다는 점이 인상적이었다. 연습문제를 풀면서 정렬 결과보다 과정 자체를 추적하는 사고 방식이 중요하다는 것을 다시 한 번 느꼈다.

---

🚀 적용점

• 데이터가 거의 정렬된 상태인 경우 삽입 정렬은 매우 효율적이다.
• 소규모 데이터 정렬이나 정렬 로직 학습용으로 적합하다.
• 다른 정렬 알고리즘(선택, 버블, 병합 정렬 등)을 이해하기 위한 기초 개념으로 활용할 수 있다.