[자료구조] 삽입정렬

삽입정렬이란?

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 "삽입"함으로써 정렬을 완성하는 알고리즘 

 

• 들어갈 위치를 선택하는데 N번, 선택하는 횟수 N번으로 O(N²)의 시간 복잡도를 가짐
• 배열이 길어질수록 효율이 떨어지지만, 구현이 간단함
• 선택정렬이나 버블 정렬에 비해 빠름

이미지 출처 : Wikipedia

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;
    }
  }
}

 

 

 

 

 

참고 | Wikipedia, fast campus 컴퓨터공학 전공 필수