Insertion Sort   삽입 정렬

(2019-12-22)
1. 삽입 정렬 (Insertion Sort)

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

  ㅇ 특징 
     - 크기가 작은 정렬 문제에 효율적
     - 버블 정렬,선택 정렬과 다음과 같이 차이가 남
        . 버블 정렬,선택 정렬이, 아직 정렬되지 않은 배열의 크기를 하나씩 줄여나가는 반면에,
        . 삽입 정렬은, 이미 정렬된 배열의 크기를 1개짜리로 시작하여 하나씩 늘려나감 

  ㅇ 계산 효율성 : O(n2)


2. 정렬 방법

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

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


3. 알고리즘 표현

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

void insertionSort (Data[],n) {
   int i,j,key ;
   for j = 2 to n
      key = Data[j] ;
      i = j - 1 ;
      while ( i > 0 and Data[i] > key )
         Data[i+1] = Data[i] ;
         i = i - 1 ;
      Data[i+1] = key ;
}


[정렬 알고리즘] 1. 정렬 알고리즘 2. 버블 정렬 3. 선택 정렬 4. 삽입 정렬 5. 병합 정렬 6. 퀵 정렬

 
        최근수정     요약목록     참고문헌