삽입 정렬이란?
삽입 정렬은 숫자 카드를 정렬하는 방법과 유사하다. 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교해 삽입할 위치를 지정한 후, 원소를 뒤(오른쪽)로 옮기고 지정된 자리에 자료를 삽입한다.
삽입 정렬 장점과 단점
| 삽입 정렬 장점 | 구현이 쉽고, 이해하기 쉽다. |
| 적은 데이터나 거의 정렬된 데이터에 대해 효율적이다. | |
| 삽입 정렬 단점 | 데이터의 양이 많아질수록 비효율적이다. |
| 최악의 경우 시간 복잡도가 O(n²)이다. |
시간 복잡도
| 알고리즘 | Best | Avg | Worst | Run-time(정수 60,000개) 단위: sec |
| 삽입정렬 | O(n) | O(n²) | O(n²) | 7.438 |
| 선택정렬 | O(n²) | O(n²) | O(n²) | 10.842 |
| 버블정렬 | O(n²) | O(n²) | O(n²) | 22.894 |
| 셸 정렬 | O(n) | O(n¹·⁵) | O(n²) | 0.056 |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n²) | 0.014 |
| 힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 0.034 |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 0.026 |
삽입 정렬 알고리즘 구현
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i]; // 선택 데이터
int j = i - 1; //비교 데이터
// 이전의 원소가 더 크다면 데이터는 하나씩 밀려난다.
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
System.out.println(Arrays.toString(arr));
}
참고자료
'🧠 Computer Science > Algorithm' 카테고리의 다른 글
| [정렬 알고리즘] 퀵 정렬(Quick Sort) (1) | 2025.02.19 |
|---|---|
| [정렬 알고리즘] 선택 정렬(Selection Sort) (0) | 2024.11.30 |
| [정렬 알고리즘] 버블 정렬(Bubble Sort) (1) | 2024.11.29 |
| [그래프 탐색 알고리즘] DFS(깊이 우선 탐색) (0) | 2024.11.21 |
| [동적 계획법] Kadane’s Algorithm (카데인 알고리즘) (0) | 2024.10.30 |
