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

---

삽입 정렬 기본

• 배열의 모든 요소를 배열의 시작부터 끝까지 현재 배열의 요소들과 비교하면서 적절한 위치에 삽입 하는 알고리즘

---

정렬 과정

과정 예시

28 13 23 25 19 : 초기 배열

28 13 23 25 19 : 2번째 자리 13 부터 시작

13 28 23 25 19 : 13은 적절한 자리를 찾아가고 다음으로 3번째 자리 23을 본다.

13 23 28 25 19 : 23도 적절한 자리를 찾아가고 다음으로 4번째 자리 25를 본다.

13 23 25 28 19 : 25도 적절한 자리를 찾아가고 다음으로 5번째 자리 19를 본다.

13 19 23 25 28 : 정렬 완료

---

시간 복잡도

• $O(N^2)$

---

구현

void insertionSort(int[] arr)
{

   for(int index = 1 ; index < arr.length ; index++){

      int temp = arr[index];
      int aux = index - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux+1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

---