정렬 알고리즘-삽입 정렬 알고리즘

알고리즘 선택 시 참고할 수 있는 선택 기준. (출처 - 그림으로 정리한 알고리즘과 자료구조)

 

상황	정렬 알고리즘
항목이 몇 개 되지 않는다.	삽입 정렬
항목이 대부분 정렬되어 있다.	삽입 정렬
최저 상황을 고려해야 한다.	힙 정렬
평균 정렬 결과가 필요하다.	퀵(빠른) 정렬
항목을 조밀한 모집단에서 가져왔다.	버킷 정렬
가능한 짧은 코드를 선호한다.	삽입 정렬

실제 정렬을 하기 위해서는 직접 프로그램을 만드는 경우는 없고 대부분은 라이브러리를 가져와서 쓴다.

 

 

 

책에서는 실제로는 라이브러리에서 가져와서 쓴다고하지만 기술면접이나 코딩테스트, 그리고 적용에 있어서도 쓰는방법은 알아둬야하기때문에 정리해두려고한다.

 

위의 표에서 보면 여러 상황에서 삽입정렬을 쓴다.

 

삽입 정렬 알고리즘은 교환 정렬 알고리즘과 비슷하다. 교환 정렬 알고리즘과 다른 점은 위치 교환이 발생한 것을 대상으로 주변의 것과 비교하여 위치를 교환하는 알고리즘이라는 것.

시간 복잡도는 최악의 경우 n(n-1)/2 이므로 O(n^2)

배열이 길어질수록 하나하나 비교해가며 나아가는 알고리즘이기때문에 효율은 떨어진다. 구현은 단순한 편이다.

 

구현할 때 앞의 요소와 비교하기때문에 index는 0이 아닌 1부터 시작한다. 

 

C로 구현한 내림차순 삽입 정렬

#include <stdio.h>
 
int main() {
  
  int arr[10] = { 9, 17, 5, 6, 124, 112, 1, 3, 87, 55 };
  int temp; // 두 값을 바꿀 때 사용할 변수
  int length = sizeof(arr) / sizeof(int);
    int j;
    
    int i;
 
    for(i = 1; i &lt; length; i++){
        temp = arr[i];
        j = i - 1;
        while(j &gt;= 0 &amp;&amp; arr[j] &lt; temp){
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = temp;
    }
    for(i = 0; i &lt; length; i++){
        printf("%d ", arr[i]);
    }
  return 0;
}