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. 퀵 정렬
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
        2.   알고리즘 종류
              1. 알고리즘 분류
              2. 그래프 알고리즘
          1.   기초 알고리즘
          2.   정렬 알고리즘
            1.   1. 정렬 알고리즘
                2. 버블 정렬
                3. 선택 정렬
                4. 삽입 정렬
                5. 병합 정렬
                6. 퀵 정렬
          3.   검색 알고리즘
        3.   알고리즘 전략
        4.   (기타 알고리즘)
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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