정리정리정리

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

JAVA/정렬

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

_JSPark 2016. 5. 31. 23:16

삽입정렬(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;

   }

 }













참고.

위키백과.

0 Comments
댓글쓰기 폼