JAVA - 정렬 알고리즘 삽입정렬

삽입 정렬

삽입 정렬은 아래의 알고리즘을 따릅니다.

 

{8, 2, 1, 4, 5} 형태의 배열을 정렬해보는 예제입니다.

두번째 인덱스인 1의 데이터를 하위 인덱스 0까지 비교합니다.

비교하는 하위 인덱스의 값이 임시 temp값보다 작을때까지 비교하고 작지 않다면 다음 인덱스로 넘깁니다.

arr[i+1] = arr[i];

이 행동으로 배열 끝까지 진행합니다.

처음 큰 한바퀴가 진행되면 위 그림의 순서대로 정렬이 진행됩니다.

 

 

다음은 기준 인덱스가 하나 증가하여 2번째 인덱스를 0~1번째 인덱스까지 비교하고 정렬합니다.

 

 

다음은 기준 인덱스가 하나 증가하여 3번째 인덱스부터 하위 인덱스까지 비교합니다.

 

다음은 기준 인덱스가 하나 증가하여 4번째 인덱스부터 하위 인덱스까지 비교합니다.

정렬이 끝나면 아래와 같이 1,2,4,5,8의 형태로 배열이 정리가 됩니다.

 

JAVA Source

public class Sorting2 {
	public static void main(String[] args) {
		int[] arr = {8, 2, 1, 4, 5};
		
		if(arr.length > 1) {
			int i, j;
			for(i=1; i<arr.length; i++) {
				int tmp = arr[i];
				for(j=i-1; j>=0; j--) {
					arr[j+1] = arr[j];
					if(tmp > arr[j]) {
						break;
					}
				}
				arr[j+1] = tmp;
			}
		}
		
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]);
			if(i+1 != arr.length) {
				System.out.print(", ");
			}
		}
	}
}