알고리즘 요약
삽입정렬 (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): # a는 숫자열
ln = len(a) # 배열의 길이
for i in range(1, ln): # 1부터 배열 길이 만큼 루프
j = i # j 에 비교 시작 위치값 대입
while j > 0 and a[j - 1] > a[j]: # 위치값이 0보다 크고 앞쪽 값보다 작으면 계속 루프
a[j - 1], a[j] = a[j], a[j - 1] # 앞뒤 서로 값 바꿈.
j -= 1 # 값 비교위치를 한칸 앞으로 이동
return a # 소팅된 결과값 리턴
print(insertion_sort([5, 2, 3, 4, 1])) # 결과는 [1, 2, 3, 4, 5]
#include <stdio.h>
void insertion_sort(int a[], int len) {
int i, j, tmp;
for (i = 1; i < len; i++) { // 1부터 배열길이 만큼 루프
j = i; // j 에 비교 시작 인덱스값 대입
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]); // 결과: 1 2 3 4 5
}