Insertion Sort (삽입 정렬)

Insertion Sort (삽입 정렬)

• 자신과 앞의 원소의 크기를 비교하여 자신의 위치에 삽입하는 정렬 방식

• 장점 : 인덱스 수가 적을 경우나 대부분 정렬되어 있을 경우 효율적이다.

• 단점 : 비교적 많은 인덱스의 이동으로 인덱스 수가 많은 경우 비효율적이다.

• 시간복잡도 : Best T(n) = n-1 = O(n)

                            Worst T(n) = n(n-1)/2 + 2(n-1) = O(n^2)

• 동작 순서 (최소 선택 정렬을 예시로 함.)

  1. 두 번째 인덱스부터 앞쪽 자료와 크기를 비교한다.
  2. 자신의 위치에 삽입 한다.
  3. 세 번째 인덱스부터 위 정렬을 반복한다.
  4. 반복.

• Code

  #include <stdio.h>                                    // 헤더파일 선언
  #define ARRAY_SIZE 10                                 // ARRAY SIZE 10으로 정의
  // Logic 부-------------------------------------------
  void insertion_sort(int array[], int n)               // 삽입 정렬 함수 및 인수 선언
  {
      int i, j, temp;                                   // 정수형 변수 i, j, temp 선언
      for(i=1;i<n;i++)                                  // 1 부터 n 까지 반복. 두 번째 인덱스부터 비교해야 함.
      {
          temp = array[i];                              // temp에 array[i] 값 대입. 키값으로 사용.
          for(j=i-1;j>=0;j--)                           // i-1 자리부터 0 자리까지 반복
          {
              if(temp<array[j])                         // temp 값이 j 자리의 값보다 작으면
              {
                  array[j+1] = array[j];                // j 자리의 값을 j+1 자리로 대입
              }
              else                                      // temp 값이 j 자리의 값보다 크면
              {
                  break;// break;
              }
          }
          array[j+1] = temp;                            // for문의 j--로 되어있기 때문에 j+1 자리에 temp 대입.
      }
  }
  // Main 부--------------------------------------------
  void main()
  {
      int Arr[ARRAY_SIZE] = {3,6,8,4,5,7,0,1,2,9};      // Arr 선언 및 임의의 값 대입
      insertion_sort(Arr, ARRAY_SIZE);                  // 삽입 정렬 함수 실행
      for(int i=0;i<ARRAY_SIZE;i++)                     // ARRAY_SIZE 만큼 반복
      {
          printf("%d",Arr[i]);                          // i번째 Array 값 출력
      }
  }

  Output : 0    1    2    3    4    5    6    7    8    9

• 시행착오

  1. if(temp<array[j]) 구문에 temp 대신 array[i] 사용
         - array[j+1]에 array[j] 대입하며 array[i] 값이 변경되므로 오류.
  2. array[j+1] = temp; 구문에 j 대신 임의 변수에 j 대입하여 사용
     else 문 안에서 임의의 변수에 j값 대입.
         - 임의의 수가 array[0] 자리에 갈 때, else 문 동작하지 않아 오류.