삽입 정렬

• 삽입 정렬은 선택 정렬과 유사하지만 조금 더 효율적인 알고리즘
• 두 번째 원소부터 시작해서 그 앞의 원소들과 비교하여 삽입할 위치 지정 후 해당 위치부터 뒤로 옮기고 해당 위치에 자료 삽입
• 최선의 경우 O(N), 최악의 경우 O(N)의 시간복잡도를 가짐
• 배열안에서 교환(swap)이 일어나므로 O(N)의 공간복잡도를 가짐

코드

static void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int preIdx = index - 1;
      while( (preIdx >= 0) && (arr[preIdx] > temp) ) {    // 2.
         arr[preIdx+1] = arr[preIdx];
         preIdx--;
      }
      arr[preIdx + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

1. 두 번째 원소부터 탐색 시작으로, temp에 자리 옮길 위치 원소(index) 저장. 그리고 preIdx에는 해당 위치(index)의 이전 위치(preIdx)부터 비교하기위해 저장
2. 이전 위치(preIdx)가 음수가 되지 않고, 이전 위치(preIdx)가 해당 위치(index)보다 크면 이전 위치(preIdx)는 한칸 뒤로. 그리고 비교할 원소 한칸 앞으로 이동(preIdx--)
3. while문이 끝나면 preIdx의 원소값보다 큰 값인 상태이기 때문에 preIdx+1 위치에 temp값 삽입