삽입정렬이란?
삽입 정렬은 각 순회에서 하나의 배열 요소를 취하여 이미 정렬된 배열 부분에 적절한 위치를 찾아 삽입하는 방식으로 작동합니다. 이 과정을 배열의 모든 요소가 정렬될 때까지 반복합니다. 삽입 정렬은 특히 작은 데이터 세트 또는 거의 정렬된 데이터에 매우 효율적인 알고리즘입니다.
삽입 정렬의 작동 방식
삽입 정렬은 다음과 같은 단계로 진행됩니다:
- 배열의 두 번째 요소부터 시작하여 각 요소를 살펴봅니다.
- 현재 요소를 임시 변수에 저장하고, 이미 정렬된 배열 섹션에서 이 요소보다 큰 요소들을 한 칸씩 뒤로 이동시킵니다.
- 임시 변수에 저장된 요소를 적절한 위치에 삽입합니다.
- 이 과정을 배열의 마지막 요소까지 반복합니다.
정렬 알고리즘 비교
| 정렬 알고리즘 | 최선 시간 복잡도 | 평균 시간 복잡도 | 최악 시간 복잡도 | 공간 메모리 | 추가 정보 |
| 선택정렬 | O(n2) | O(n2) | O(n2) | O(1) | 제자리 정렬(안전) 비교적 구현이 간단 |
| 삽입 정렬 | O(n) | O(n2) | O(n2) | O(1) | 제자리 정렬(안전) 작은 데이터 세트나 거의 정렬된 데이터에 매우 효율적 |
| 버블 정렬 | O(n) | O(n2) | O(n2) | O(1) | 제자리 정렬, 매우 비효율적, 데이터가 거의 정렬된 상태에서 효율적 |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n**2) | O(nlogN) | 공간 복잡도는 재귀 깊에 따라 달라짐, 평균적으로 가장 빠름 |
| 힙 정렬 | O(nlogn) | o(nlogn) | O(nlogn) | O(1) | 힙 구조를 사용, 데이터 크기에 따라 일정하게 빠름 |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O(nlogn) | 외부 메모리 사용, 대규모 데이터에 효율적, 안정 정렬 |
| 팀 정렬 | O(n) | O(nlogn) | O(nlogn) | O(n) | 하이브리드 알고리즘, 대규모 데이터에 매우 효과적, 매우 안정적인 정렬 |
비교적으로 삽입 정렬은 작은 또는 대부분 정렬된 데이터에 대해 매우 빠르게 작동할 수 있습니다.
하지만 평균적으로나 최악의 경우에는 시간 복잡도가 O(n2)으로 나타나므로 크기가 큰 데이터 세트에서는 비효율적일 수 있습니다.
이 글을 통해 삽입 정레을 이해하고 기본적인 구현 방법을 배울 수 있었습니다. 다음 게시물에서는 이를 바탕으로 삽입 정렬을 코드로 표현해보겠습니다. 코드 표현의 구성은
1. 반복문
2. 재귀함수 2개
3. 재귀함수 1개
4. 반복문을 활용한 시각화
로 이루어져있으며 이를 자세하게 살펴보겠습니다.
'Data Structure' 카테고리의 다른 글
| 정렬 | 병합정렬 | 안정적이고 강력한 정렬 알고리즘 (0) | 2025.02.13 |
|---|---|
| 정렬 | 삽입정렬 | 특이 case 에 적합한 정렬 (3) | 2025.01.23 |
| 누구나 구현 할 수 있는 알고리즘 II (0) | 2025.01.20 |
| 정렬 | 선택정렬 | 누구나 구현할 수 있는 정렬 알고리즘 (0) | 2025.01.20 |
| 재귀 함수 III (2) | 2025.01.15 |