CS학습
삽입 정렬(Insertion Sort): 정렬되지 않은 데이터를 하나씩 선택하여 정렬된 부분에 삽입하는 알고리즘
삽입 정렬은 간단하면서도 직관적인 정렬 알고리즘으로, 작은 데이터셋에 효과적입니다. 배열의 이미 정렬된 부분을 유지하면서, 아직 정렬되지 않은 요소를 반복적으로 삽입하여 정렬을 완료합니다. 제자리 정렬(in-place sort) 알고리즘이며, 안정 정렬(stable sort)입니다.
송민성2분 읽기
1. 개념
삽입 정렬(Insertion Sort)은 배열을 순회하며 이미 정렬된 부분 배열을 유지하고, 아직 정렬되지 않은 요소를 적절한 위치에 삽입하여 정렬을 진행하는 알고리즘입니다. 카드 게임에서 패를 정렬하는 방식과 유사하게 작동합니다.
2. 왜 사용하는가
- 구현의 용이성: 알고리즘이 직관적이고 이해하기 쉬워 구현이 간단합니다.
- 작은 데이터셋: 데이터의 크기가 작을 때 성능이 좋습니다. (O(n^2)이지만 상수 시간이 작음)
- 거의 정렬된 데이터: 데이터가 거의 정렬된 상태일 때 매우 효율적입니다. (최선의 경우 O(n))
- 안정 정렬: 동일한 값의 요소의 순서가 유지됩니다.
3. 동작 원리
- 배열의 두 번째 요소부터 시작합니다.
- 현재 요소를 이전 요소들과 비교하며, 삽입할 위치를 찾습니다.
- 삽입할 위치를 찾으면, 해당 위치 이후의 요소들을 한 칸씩 뒤로 이동합니다.
- 현재 요소를 찾은 위치에 삽입합니다.
- 배열의 끝까지 위 과정을 반복합니다.
4. 코드 예제
python
def insertion_sort(arr):
"""
삽입 정렬 알고리즘 구현
"""
n = len(arr)
for i in range(1, n):
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
# 예제
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print(sorted_arr) # 출력: [5, 6, 11, 12, 13]5. 시간 복잡도 또는 성능 특성
- 최선의 경우: O(n) - 배열이 이미 정렬된 경우
- 평균의 경우: O(n^2)
- 최악의 경우: O(n^2) - 배열이 역순으로 정렬된 경우
- 공간 복잡도: O(1) - 제자리 정렬(in-place sort)
6. 실무 사용 사례
- 작은 데이터셋 정렬: 데이터의 크기가 작고 성능이 크게 중요하지 않은 경우
- 거의 정렬된 데이터 정렬: 데이터가 이미 대부분 정렬되어 있는 경우
- 온라인 정렬: 데이터 스트림이 들어올 때 실시간으로 정렬해야 하는 경우 (예: 검색어 자동 완성)
7. 주의할 점
- 데이터셋이 크면 성능이 저하될 수 있습니다.
- 다른 정렬 알고리즘 (병합 정렬, 퀵 정렬 등)에 비해 성능이 떨어질 수 있습니다.
8. 핵심 정리
삽입 정렬은 구현이 간단하고 작은 데이터셋에 유용한 정렬 알고리즘입니다. 이미 정렬된 데이터나 거의 정렬된 데이터에 대해서는 효율적으로 동작하지만, 큰 데이터셋에서는 성능이 저하될 수 있습니다. 제자리 정렬이며 안정 정렬이라는 특징을 가지고 있습니다.