알고리즘
정렬(Sorting) - 삽입 정렬 (Insertion Sort)
dyeoma
2020. 7. 31. 10:40
단계
삽입 원소를 기존의 정렬된 부분 리스트 속에 끼워 넣기
삽입 원소의 위치를 옮기면서 처음 단계의 insert 반복 적용
분석
$\sum_{i=1}^{n-1}(i+1)=n^2$ → O($n^2$)
최선 : 오름차순으로 정렬된 상태
최악 : 내림차순으로 정렬된 상태
data 양이 적을 때 사용하면 빠름
삽입 정렬 (Insertion Sort)
기본 단계 insert 함수 template void Insert (const T& e, T* a, int i) { // 정렬된 리스트에 e 삽입 // a[0] = -∞; while (e < a[i]){ a[i+1] = a[i]; i--; } a[i+1] = e; } 최악 : i+1 삽입 정렬 함수 templa..
dyeoma.tistory.com