기본 단계 insert 함수
template <class T>
void Insert (const T& e, T* a, int i) { // 정렬된 리스트에 e 삽입
// e = 끼워넣을 값
// a = 배열
// i = 현재까지 정렬된 index
// a[0] = -∞;
while (e < a[i]){
a[i+1] = a[i];
i--;
}
a[i+1] = e;
}
최악 : i+1
삽입 정렬 함수
template <class T>
void InsertionSort (T* a, const int n) { // a[1:n] 오름차순 정렬
for (int j=2; j<=n; j++) {
T temp = a[j];
insert(temp, a, j-1);
}
}
분석
∑n−1i=1(i+1)=n2 → O(n2)
최선 : 오름차순으로 정렬된 상태
최악 : 내림차순으로 정렬된 상태
'알고리즘 > C++' 카테고리의 다른 글
합병 정렬 (Merge Sort) (0) | 2020.08.17 |
---|---|
퀵 정렬 (Quick Sort) (0) | 2020.07.31 |
이진 탐색 (Binary Search) 알고리즘 (0) | 2020.07.30 |
순차 탐색 (Sequential Search) 알고리즘 (0) | 2020.07.30 |
Ford 알고리즘 (0) | 2020.07.28 |