정렬 알고리즘 - 삽입 정렬 (Insertion Sort)

 

 

삽입 정렬은 선택한 요소를 자신보다 더 앞쪽 정렬된 부분의 알맞은 위치에 삽입하며 정렬해 나간다.

최선의 경우 O(n) / 평균, 최악 O(n^2)의 시간복잡도를 가진다.

 

1) 정렬이 되지 않은 부분의 가장 첫 번째 요소 selection[i]를 선택하고

2) 앞쪽 정렬된 부분의 알맞은 위치에 삽입한다.

 2-1) 정렬된 부분을 한 칸씩 뒤로 밀어내며 이동하고

 2-2) selection[i]보다 작은 요소를 만날 때까지

 2-3) 혹은 가장 앞에 도달할 때까지 이동하여 삽입한다.

 

 

void insertionSort(int[] arr){
   for(int i = 1 ; i < arr.length ; i ++){
      int temp = arr[i]; //selection[i]
      int j = i - 1; //정렬된 부분의 마지막
 
      while((j >= 0) && (arr[j] > temp)) {
         arr[j+1] = arr[j--];
      }
 
      arr[j+1] = temp;
   }
}

 

동일한 값에 대해 기존의 순서가 뒤바뀌지 않는 안정된 정렬!