삽입 정렬

삽입 정렬(insertion sort)

삽입 정렬은 배열의 각 데이터를 기준으로 좌측 지점을 탐색하여 데이터를 정렬 가능한 위치에 삽입하는 방식으로 정렬을 수행한다. 다음 순서에 따라 정렬을 수행한다.

1. 기준 위치의 데이터를 백업한다.

2. 기준 위치보다 좌측의 데이터와 비교하여 삽입 지점을 갱신한다.

3. 더이상 데이터가 없거나 기준 위치의 데이터보다 작은 데이터를 만날 경우 탐색을 중지하고 데이터를 해당 지점에 삽입한다.

4. 기준 위치를 다음 칸으로 변경한다.

5. 1번으로 이동한다.

샘플 데이터

정렬을 위해 사용할 데이터는 다음과 같다.

int[] data = new int[]{30, 50, 20, 10, 40};

삽입 정렬은 모든 데이터를 한 번씩 기준으로 진행하므로 샘플 데이터의 길이만큼 5회차로 진행한다.

1회차

• 기준점 : data[0] 좌측에 데이터가 존재하지 않기 때문에 수행할 내용이 없다.

2회차

• 기준점 : data[1] data[1] 지점의 50을 백업하고 좌측인 data[0]과 비교하지만 앞의 데이터가 더 작기 때문에 위치 변경은 수행하지 않는다.

3회차

• 기준점 : data[2] data[2] 지점의 20을 백업하고 좌측인 data[1], data[0]과 비교하여 data[0] 지점으로 삽입한다.

4회차

• 기준점 : data[3] data[3] 지점의 10을 백업하고 좌측인 data[2], data[1], data[0]과 비교하여 data[0] 지점으로 삽입한다.

5회차

• 기준점 : data[4] data[4] 지점의 40을 박업하고 좌측인 data[3], data[2], data[1], data[0]과 비교해야 하지만 data[2]가 30이므로 data[3] 지점에 삽입한다.

전체

int[] data = new int[] {30, 50, 20, 10, 40};

//정렬
for(int k=0; k < data.length; k++) {
	int index = k;
	int backup = data[k];
	for(int i=k-1; i >= 0; i--) {
		if(backup < data[i]) {
			index = i;
			data[i+1] = data[i];
		}
		else {
			break;
		}
	}
	
	data[index] = backup;
}

//출력
for(int i=0; i < data.length; i++) {
	System.out.println(data[i]);
}