삽입 정렬 (Insertion Sort) - JAVA

삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법입니다.

시간 복잡도는 O(n²)이지만 구현하기 쉽습니다.

 

정렬 과정

출처 : https://www.digitalocean.com/community/tutorials/js-bubble-selection-insertion-sort

1. 현재 index에 있는 데이터 값 선택
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치 탐색
3. 삽인 위치부터 index에 있는 위치 까지 shift 연산
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++
5. 선택할 데이터가 없을 때까지 반복

 

소스 코드

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;
   }
}