Processing math: 100%
본문 바로가기

알고리즘/C++

삽입 정렬 (Insertion Sort)

기본 단계 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);
   }
}

 

 

분석

n1i=1(i+1)=n2  → O(n2)

최선 : 오름차순으로 정렬된 상태

최악 : 내림차순으로 정렬된 상태

'알고리즘 > C++' 카테고리의 다른 글