[알고리즘] 기초 정렬 알고리즘 - 삽입 정렬(Insertion Sort)

 

 

삽입정렬

주어진 배열 a[]를 그대로 사용

전체 배열중에서 정렬되지 않은 부분의 첫번째 원소를 "꺼내서" 정렬된 부분의 알맞은 위치에 삽입

이때, 전체배열은, 정렬 된 부분 / 삽입할 원소(꺼낸 원소) / 정렬 안 된 부분 으로 나뉜다.

 

레코드를 계속 이동시켜야 하므로 레코드의 크기가 큰 경우에 불리

almost sorted file인 경우에 유리

실행시간은 입력자료의 순서에 민감

안정적인 알고리즘

제자리 정렬

- 비교시 배열의 범위를 벗어나는것을 방지하기 위해 감시 키 필요

   a[0]자리에 가장 작은값보다 더 작은 값을 넣어서 경계키로 사용

 

초기에 a[1]은 삽입되어있는 상태,

a[2]를 꺼내서 a[1]의 값과 비교, 알맞은 순서로 삽입

(이 과정에서 a[2]가 a[1]의 값 보다 작다면 a[1]을 꺼내서 a[2]의 자리에 넣고,

a[2]에서 꺼낸 원소를 a[1]의 자리에 넣는다.)

두번째 단계에서는 a[3]의 원소를 꺼내 a[1], a[2]의 배열 중 들어갈 자리가 있는 지 확인,

없으면 다시 a[3]의 자리에 넣고 있다면, a[1]~a[2]의 원소들을 한칸씩 옮겨가며 자리를 확보->삽입

..

..

..

마지막에 a[n]의 원소를 a[1]~a[n-1]까지의 배열 사이에 순서에 알맞게 들어갈 자리가 있는지 확인,

있다면 원소를 한칸씩 옮기며(이때 교환이 아니라 이동이라는걸 명심, 앞 부분은 이미 정렬된 순서)

알맞은 위치의 공간을 확보한 후 삽입.

만약 a[n-5]자리에 a[n]에서 꺼낸 원소가 들어가야 한다면,

a[n-1]의 원소를 a[n]자리로

a[n-2]의 원소를 a[n-1]의 자리로

a[n-3]의 원소를 a[n-2]의 자리로

a[n-4]의 원소를 a[n-3]의 자리로

a[n-5]의 원소를 a[n-4]의 자리로 옮긴 후

a[n-5]의 자리에 a[n]에서 꺼낸 원소를 삽입

..

시간복잡도는 O(N^2)

 

InsertionSort(a[], n)  {      // 원소 v는 a[i], 1 <= i <= n,      // 원소 v(=a[i], 1 <= i, 1 <= i <= n)를 부분배열 a[1 : i-1]에 오름차순 순으로 삽입      for ( i <- 2; i <= n; i <- i+1 ) do { // 두 번째 원소 a[2]부터         v <- a[i]; // v는 임시 저장공간         j <- 1; -        while ( a[j-1] > v ) do {              a[j] <- a[j-1]; // a[j-1];          } / while 문          A[j] <- v;  // v를 빈자리에 삽입  } // for  end InsertionSort()  }