[자료구조] Insertion Sort 삽입정렬

삽입정렬

• 새로운 레코드를 i개의 정렬된 레코드 리스트에 끼워 넣어 크기가 i+1인 정렬된 결과 레코드 리스트를 만든다.
  

    // e를 정렬된 리스트 a[1:i]에 삽입하여 결과
    // 리스트 a[1:i+1] 도 정렬되게 한다
    // 배열 a는 적어도 i+2 원소를 포함할 공간을 가지고 있어야 함
    
    template<class T>
    void Insert(const T& e, T* a, int i){
        a[0] = e; // 맨 처음 a[0] 값
    		// a[0]를 사용함으로써 end-of-list 검사 (i <1)을 생략할 수 있게 하여 while 루프 간단하게 한다 
        while(e < a[i]){  // e 가 a[i]보다 작으면
            a[i+1] = a[i]; // 한칸씩 밀어낸다
            i--;
        }
        a[i+1] = e; // e를 원하는 위치에 넣는다 
    }

    template <class T>
    void InsertionSort(T* a, const int n){
        for (int j = 2; j<=n; j++){ // 2부터 n까지 가면서
            T temp = a[j]; // a[j]를 임시값으로 해놓고
            Insert(temp, a, j-1); // temp를 이 위치에다가 넣어봐 // n-1 번 반복한다
        }
    }

• Insert(e, a, i)는 최악의 경우 삽입 전 i+1번 비교해야 한다
  ⇒ Insert의 복잡도 O(i)

• InsertionSort의 복잡도

  • i = j-1 = 1, 2, ..., n-1 일 때 Insert 호출
  • 복잡도 = O($\Sigma_{i=1}^{n-1}(i+1)$) = $O(n^2)$

• 삽입 정렬의 최악의 예
  - 입력 리스트가 역순인 경우, 새로운 레코드가 정렬된 부분에 삽입될 때 마다 정체 정렬된 부분이 오른쪽으로 이동
  
  

• n = 5, 입력 키 순서가 2, 3, 4, 5, 1 인 경우

  • j = 2, 3, 4 에 대한 시간 : O(1)
  • j = 5 에 대한 시간 : O(n)

• 삽입 정렬의 변형

  • 이원 삽입 정렬
    • Insert에서 사용된 순차 탐색 기법 대신 이원 탐색 Binary Search 을 사용
    • 삽입 정렬에서 수행하는 비교 횟수를 줄인다
    • 레코드 이동횟수는 변하지 않음
  • 연결 삽입 정렬
    • 리스트의 원소들을 배열 대신 연결리스트로 표현
    • 링크 필드만 조정하면 되므로 레코드 이동 횟수가 0