insertion_sort (1) 썸네일형 리스트형 [C언어/파이썬] Insertion Sort Algorithm C와 Python으로 구현해보기 - 배열 맨 처음 정렬된 부분에 정렬되지 않은 다음 항목들을 반복적으로 삽입하는 방식이다. - 즉 미리 정렬된 리스트에 새 항목을 추가할 때 좋은 정렬 알고리즘이다. - 데이터의 크기가 작고 리스트가 이미 정렬되어있으면 다른 merge sort 나 quick sort 같은 고급 알고리즘보다 성능이 좋음 - 최선의 경우 시간복잡도 O(n) - 평균과 최악의 경우 시간복잡도 O(n^2) 1. insertion sort ( 삽입 정렬 ) 알고리즘 process index 0 1 2 3 4 5 11 3 28 43 9 4 를 정렬한다고 가정 outer loop i : 0 ~ 5 0 번부터 5번 인덱스 i 가 차례로 리스트에 추가된다고 가정한다. 인덱스 i 가 추가될 때에는 0~ i-1 까지는 정렬되어 있다고 가정.. 이전 1 다음