삽입정렬(Insertion Sort)이란 무엇일까?

삽입정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 해당 원소의 값과 앞의 원소들의 값을 비교해나가며 자신의 위치를 찾아서 삽입한다.
• 삽입을 하기 위해 데이터들의 이동이 불가피하여 데이터 양이 많아질 수록 효율이 저하된다.

시간복잡도

• O(n^2)

이해를 돕는 이미지

출처 - 위키백과

이해를 돕는 영상

 

[C 코드]

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ){
    	//선택된 원소값이 비교하는 원소의 값보다 작으면 앞부분으로 삽입
        data[j+1] = data[j];
        data[j] = remember;
    }
  }
}