1-3) [C]삽입정렬(Insertion Sort)

1) 삽입정렬이란?

왼쪽부터 순서대로 정렬하는 방식으로 좌측에는 정렬이 끝난 숫자가 오게 되고 우측에는 아직 확인하지 않은 숫자가 남게됨

우측의 미탐색 영역엣 숫자를 하나 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식

2. 미탐색 숫자 중에서 가장 왼쪽에 있는 2와 정렬된 5를 비교하여 더 작은 수를 왼쪽으로 보낸다.

5. 3보다 작은 2가 왼쪽에 있으므로 비교를 멈추고 정렬 완료로 간주한다.

2) 삽입정렬의 시간복잡도

삽입정렬에서는 각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교한다. 만약 왼쪽에 있는 숫자가 작다면 교체가 발생하지 않고 라운드를 종료한다.

하지만 꺼낸 숫자가 정렬 완료 영역의 숫자보다 작을 때는 그 숫자가 가장 왼쪽에 도착할 때까지 비교와 교체 작업을 한다. k라운드에서는 k-1회씩 작업한다. 따라서 최악의 경우에는 2라운드에서 1회, 3라운드에서 2회, ..., n라운드에서 n-1회의 비교와 교체가 발생하므로 계산 시간이 버블 정렬이나 선택 정렬과 같이 O(n^2)이다. 그리고 최악의 입력 데이터는 마찬가지로 역순으로 나열된 경우이다.

3) 삽입정렬 구현

#include <stdio.h>

int main(void){
  int data[6] = {5, 2, 3, 6, 4, 1};
  int keyValue;
  int j;
  printf("Before sorting :\n");
  
  for(int i =0; i<6;i++){
    printf("%d",data[i]);
  }
  printf("\n");
  for(int i=0; i<5;i++){ 
      keyValue=data[i+1];
      for(j=i;j>=0;j--){ //keyValue 앞의 숫자들 확인
          if(data[j]>keyValue){ 
              data[j+1]=data[j];
          }
          else{
              break;
          }
        }
        data[j+1]=keyValue;
    } 
        
  printf("After sorting :\n");
  for(int i=0; i<6;i++){
      printf("%d",data[i]);
  }
  
  return 0;
  }

결과화면

Before sorting :
523641
After sorting :
123456

1) 삽입정렬이란?

2) 삽입정렬의 시간복잡도

3) 삽입정렬 구현

티스토리툴바