[JAVA] 삽입 정렬(Insertion Sort)

예제 배열 {5, 4 , 7, 3, 6}

1~4회전까지의 결과가 위와 같이 나오도록 해보자

package jungbo;

public class T24InsertionSort {

public static void main(String[] args) {

int array[] = {5, 4, 7, 3, 6};

int key;

int i, j;

int cnt;

for(i=1;i<=4;i++){

key = array[i];

for(j=i-1;j>=0;j--){

if(array[j]<key){break;}

else{array[j+1]=array[j];}

}

array[j+1]=key;

for(cnt=0;cnt<=4;cnt++){

System.out.printf("%2d", array[cnt]);

}

System.out.println();

}

}

}

삽입정렬 방법

1회전 

배열의 2번째 요소를 선택하여 임시공간(KEY)에 저장한다.

임시공간에 저장된 값(KEY)과

원래 그 요소가 있었던 자리보다 왼쪽에 있는 값과 비교하여

비교된 대상이 배열의 오른쪽 방으로 이동하고

이동이 끝나면 KEY 값이 비어있는

가장 왼쪽 공간으로 들어간다.

2회전~

배열의 3번째 요소를 선택하여 임시공간(KEY)에 저장한다.

(KEY)값과

원래 그 요소가 있었던 자리보다 왼쪽에 있는 값 전부와

왼쪽으로 이동하며 하나 하나 대조하여

비교된 값이 임시공간에 저장된 값(KEY)보다 크면 

배열의 오른쪽 방으로 이동한다.

이동이 끝나면 KEY 값이 비어있는 

가장 왼쪽 공간으로 들어간다.