Insertion Sort   삽입 정렬

(2022-07-09)

1. 삽입 정렬 (Insertion Sort)

  ㅇ 선택한 요소를 순서가 올바른 위치로의 삽입을 반복적으로 수행

  ㅇ 특징 
     - 크기가 작은 정렬 문제에 효율적
     - 버블 정렬,선택 정렬과 다음과 같이 차이가 남
        . 버블 정렬,선택 정렬이, 
           .. 아직 정렬되지 않은 배열의 크기를 하나씩 줄여나가는 반면에,
        . 삽입 정렬은, 
           .. `정렬을 끝낸 배열`,`정렬을 해야 할 배열` 2개 그룹으로 구분시키고,
           .. 이미 정렬된 배열 크기 1개짜리로 시작하여, 하나씩 늘려나감 
     - in-place 정렬
     - 안정 정렬계산 효율성 
     - Worst : O(n2)
        . i=1일때 1번,i=2일때 2번,...,i=n-1일때 n-1번
        . 따라서, 1+2+...+(n-1) = n(n-1)/2번의 비교 필요
     - Best  : Ω(n) 
        . 이미 정렬된 경우


2. 정렬 방법

  ㅇ 입력 배열  또는 정렬되지 않은 배열에서 차례대로 원소를 뽑아서, 
     - 정렬된 배열의 적절한 위치에 삽입하면서, 이를 반복적으로 수행
     - 이 과정에서, 삽입된 수 보다 큰 수들은 한칸 씩 우측으로 밀려나감
        . 앞쪽 Data[1,..,j-1]은, 정렬된 배열이 되고,
        . 뒤쪽 Data[j+1,...,n]은, 아직 미정렬 배열이 됨

  ㅇ 2개의 중첩 루프 사용
     - 외부 루프는, for 문 사용
        . (입력 배열 크기 - 1) 만큼 순환
     - 내부 루프는, for 문 또는 while 문 사용


3. 알고리즘 표현

    
Input  : 정렬 전 Data[], int n
Output : 정렬 후 Data[]

void insertionSort (int Data[], int n) {
    int i = 0;                    // i : 삽입 전 인덱스
    int j = 0;                    // j : 삽입 인덱스
    int key = 0;                  // key : 비교할 키값
    for (i = 1; i < n; i++) {     // 인덱스 0은 이미 정렬되어 제외. n-1회 반복.
        key = Data[i];            // 삽입하고 싶은 키값
        for (j = i - 1; j >= 0 && Data[j] > key; j--) {
            Data[j+1] = Data[j];  // 키값이 작으면, 하나씩 뒤로 이동
        }
        Data[j+1] = key;          // 제 위치인 j+1번째로 키값을 가져옴
    }
}



Copyrightⓒ written by 차재복 (Cha Jae Bok)
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"