[알고리즘-3] 삽입정렬

안녕하세요 기린입니다 :)

지난 시간까지 선택 정렬과 버블 정렬에 대해 알아보았습니다.

앞에서 다룬 정렬 알고리즘은 모두 시간 복잡도 모두 O(N^2)을 가진다는 점에서 비효율적이라 할 수 있죠.

이번시간에 다룰 삽입 정렬은 어떨지 한번 보겠습니다.

문제는 지난 시간과 동일합니다.

 

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 10 5 8 7 6 4 3 2 9

 

삽입 정렬은 위 문제를 풀 때 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결합니다. 자 여기서 다른 알고리즘들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 '필요할 때만' 위치를 바꾸게 되는데요

먼저, 소스 코드를 살펴 보겠습니다.

#include <stdio.h>

int main(void) {
  int i, j, temp;
  int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; 
  for(i = 0; i < 9; i++) { 
    j = i;
    while(j >= 0 && array[j] > array[j + 1]) {  
      temp = array[j]; 
      array[j] = array[j + 1];
      array[j + 1] = temp;
      j--; 
    } 
  } 
  for(i = 0; i < 10; i++) { 
    printf("%d ", array[i]); 
  } 
  return 0;
}

자 삽입 정렬은 비교적 느린 정렬 알고리즘에 속하지만 쉽게 생각 할 수 없는, 조금은 복잡한 구조를 가지고 있습니다.

삽입 정렬은 기본적으로 '정렬이 되어있다'고 가정을 한다는 점에서 특정한 경우에서는 굉장히 빠른 속도를 자랑합니다.

일단 소스코드상 반복문이 두 번 들어가기에 시간 복잡도는 O(N^2) 입니다.

삽입 정렬의 시간 복잡도는 O(N^2) 입니다.

하지만, 데이터가 거의 정렬되어 있는 상태라면 어떤 알고리즘이 가장 효율적일까 생각해보면

무조건 정렬하는 선택, 버블 정렬 보다는 필요할 때만 정렬하는 삽입 정렬을 사용하게 되면 그 효율의 차이는 엄청날 것입니다.

즉, 특정 조건에서는 가장 빠르게 정렬할 수 있는 특징을 가지고 있다고 할 수 있죠.

이해가 되셨나요 ? :)

자 다음 시간에는 퀵 정렬에 대해 알아보겠습니다

자 그럼 즐거운 코딩하세요 !

 

문의: ralla0405@gmail.com