삽입정렬 (Insert Sort)

#정의: 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입하는 정렬

- 1단계 : list[1]을 list[0]과 비교하여 만약 뒤 list[1] 데이터가 값이 더 작으면 바꾼다

               (swap list[2]와 list[1]) >> 이 과정을 거치면 list[1], list[2]는 정렬된 상태가 된다.

- 2단계 : list[2]을 list[1], list[0]과 순서대로 비교하여 만약 뒤 데이터가 값이더 작으면 바꾼다

               (swap list[i]와 list[i+1]) >> dl 과정을 거치면 list[i], i = 0,1,2는 정렬된 상태가 된다.

- 3단계 : list[3]을 list[i], i = 2,1,0 순서대로 비교하여 만약 뒤 데이터가 값이더 작으면 바꾼다

               (swap list[i]와 list[i+1]) >> 이 과정을 거치면 list[i], i = 0,1,2,3은 정렬된 상태가 된다.

…

- n-1단계 : list[n-1]을 list[i], i = n-2,n-3,…,2,1,0 순서대로 비교하여 만약 뒤데이터가 값이 더 작으면 바꾼다

              (swap list[i]와 list[i+1]) >> 이 과정을 거치면 list[i], i = 0,1,2,3,…,n-1은 정렬된 상태가 된다.

 

https://www.youtube.com/embed/ROalU379l3U

 

/* 삽입정렬 – 데이터를 앞으로 이동하면서 끼워넣는다 */

void insertion_sort(element list[], int n) {

   int i, j;

   element next;

   for(i = 1; i < n; i++) { 

      next = list[i];

      for(j = i - 1; j >= 0 && next.key < list[j].key ; j--){ 

         list[j + 1] = list[j];

      };

      list[j + 1] = next;

}