728x90
- 삽입 정렬(Insertion Sort)
i (0<i<n)번째의 요소(tmp)를 순서대로 i-1까지의 정렬된 부분의 알맞은 자리(j)에 삽입하여 정렬
void insertion(int a[], int n) {
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1]; // tmp가 더 작으므로 정렬된 부분을 한 칸씩 뒤로 미룸
}
a[j] = tmp; // 찾은 자리 j에 tmp를 넣음
}
}
시간 복잡도: O(n^2) - avg, worst (best는 O(n))
'알고리즘 > 자료구조(C)' 카테고리의 다른 글
병합 정렬(Merge Sort) (0) | 2023.09.22 |
---|---|
퀵 정렬(Quick Sort) (0) | 2023.09.22 |
선택 정렬(Selection Sort) (0) | 2023.09.22 |
버블 정렬(Bubble Sort) (0) | 2023.09.22 |
재귀 알고리즘 (0) | 2023.09.22 |