알고리즘 요약
삽입정렬 (insertion sort)
-배열의 앞쪽 부터 차례로 정렬되지 않은 값들을 앞쪽 정렬된 값과 비교해서 정렬한다.
-시간복잡도: 경우에 따라 O(n) 또는 O(n²)
-데이터가 작고 정렬되어 있으면 성능이 좋다.
정렬 과정 설명
① ② ③ ④ ⑤ : 위치번호
[3, 2, 5, 4, 1] :숫자열이 있을 경우,
-①3과 ②2 비교해서 2가 작으니 서로 위치를 변경
[2, 3, 5, 4, 1]
-②3과 ③5 비교해서 5가 크니 위치 변경없음
[2, 3, 5, 4, 1]
-③5와 ④4 비교해서 4가 적으니 서로 위치 변경
[2, 3, 4, 5, 1]
-④5와 ⑤1 비교해서 1이 적으니 서로 위치변경.
[2, 3, 4, 1, 5]
-③4, ②3, ①2 와 비교해서 작으므로 위의 과정 반복하면서 위치 변경
[1, 2, 3, 4, 5] : 끝자리에서 맨앞자리 까지 작은 수를 앞으로 계속 정렬하면 최종 완료.
def insertion_sort(a):
ln = len(a)
for i in range(1, ln):
j = i
while j > 0 and a[j - 1] > a[j]:
a[j - 1], a[j] = a[j], a[j - 1]
j -= 1
return a
print(insertion_sort([5, 2, 3, 4, 1]))
#include <stdio.h>
void insertion_sort(int a[], int len) {
int i, j, tmp;
for (i = 1; i < len; i++) {
j = i;
while (j > 0 && a[j - 1] > a[j]) {
tmp = a[j - 1]; a[j - 1] = a[j]; a[j] = tmp;
--j;
}
}
}
int main() {
int i, a[] = {3, 2, 5, 4, 1}, len = sizeof(a) / sizeof(a[0]);
insertion_sort(a, len);
for (i = 0; i < len; i++) printf("%d ", a[i]);
}