삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort)  

1. n번째 원소를 기준으로 잡는다.

2. n-1번째 원소부터 역으로 첫번째 원소까지 검사를 시작한다.

3. 대상이 기준값보다 크면 대상을 뒤로 보낸다. (인덱스+1)

첫번째 원소는 정렬된 것으로 생각하며, 두번째 원소부터 연산을 시작.

정렬된 부분집합과 각 원소를 비교해나아가며 부분집합에 넣는 방식.

package algorithm;

import java.util.Arrays;

public class InsertSort01 {

public static void main(String[] args) {

int[] num = new int[]{5, 4, 2, 1, 3};

for(int i=1; i < num.length; i++) { // 1~4

int key = num[i]; 

int j = 0;

for(j=i-1; j >= 0; j--) { // j가 (i-1)부터 0까지 감소로직

if(num[j] > key) {

//key값보다 num[j]값이 크면 num[j]값을 오른쪽으로 한칸씩 이동.

num[j+1] = num[j];

}else break;

} num[j+1] = key; 

//break문이나 for문을 빠져나온 j는 key값을 넣을 인덱스에 j--가 된 상태이므로에 +1을 해준다. 

//(j--된후에 조건식을 만나기 때문에)

}

System.out.println(Arrays.toString(num));

}

}

[1, 2, 3, 4, 5]