정렬 알고리즘 - 삽입정렬(insertion sort)

삽입정렬(insertion sort)

제자리정렬, 안정정렬, 내부정렬

 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입

 초기 - [ 31, 25, 12, 22, 11 ]

     1 - [ 25, 31, 12, 22, 11 ]

     2 - [ 12, 25, 31, 22, 11 ]

     3 - [ 12, 22, 25, 31, 11 ]

     4 - [ 11, 12, 22, 25, 31 ]

 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;

   }

 }

참고.

위키백과.