[알고리즘] 삽입정렬(Insertion Sort)

삽입정렬이란 앞부분 데이터는 정렬이 되어 있다고 가정하고, 뒷부분 데이터가 정렬된 데이터중 어느 곳에 있어야 적절한지를 판단하여 절렬하는 정렬방식이다.

A[0]에는 dummy데이터 (마이너스 무한대),가 있다고 가정한다. (매번 첫번째 데이터인지 확인하지 않아서 더 효율적이다. 이때 컴퓨터에는 마이너스 무한대라는 것이 없기 때문에 정수 최대값을 사용한다.

void InsertionSort(int A[],int n){
    // 입력 : A[0:n],n:원소의 개수, A[0]:dummy
    // 출력 : A[0:n] : A[0]:dummy , A[1:n]은 정렬된 배열
    int i, j, value;
    for (i = 2; i <= n; i++){
        value = A[i];
        j = i;
        while (A[j-1]>Value){
            A[j] = A[j-1]; j--;
        }

        A[j]=value;
    }
}

• 제자리성 : 제자리 정렬 (주어진 메모리 공간 외에 추가적으로 사용하는 메모리가 없는 (상수크기) 정렬)
• 안정성 : 안정한 정렬 (인접한 레코드만 자리바꾸기 때문)
• 최악시간복잡도 = O(n^2)
  • 역순으로 이미 정렬된 레코드 i번째 키 삽입시 i번의 비교수행 (2+3+...+n = n(n+1)/2-1)
• 최선시간복잡도 = O(n)
  • 이미 정렬된 레코드 (n-1비교 수행 : 비교만 하고 자리바꿈은 일어나지 않음)
• 평균시간복잡도 = O(n^2)

 

삽입정렬은 최선 복잡도에서 성능이 좋기 때문에 자주 사용한다.

이미 어느정도 정렬된 레코드에서 효과적인 방법이다.