Insertion sort. 삽입정렬

주어진 숫자에서 두번째 자료(key)부터 앞의 자료들과 비교하며 삽입하여 정렬한다.

 

예시 ) 빨간색 : i 파란색 : j-1

8 5 6 2 4 key 5와 그 앞 8 비교 , swap

5 8 6 2 4 key 6과 그 앞 8 비교 , swap

5 6 8 2 4 key 6과 그 앞 5 비교 

5 6 8 2 4 key 2와 그 앞 8 비교, swap

5 6 2 8 4 key 2와 그 앞 6 비교, swap 

5 2 6 8 4 key 2와 그 앞 5 비교, swap

2 5 6 8 4 key 4와 그 앞 8 비교, swap

2 5 6 4 8 key 4와 그 앞 6 비교, swap

2 5 4 6 8 key 4와 그 앞 5 비교, swap

2 4 5 6 8 key 4와 그 앞 2 비교

2 4 5 6 8

import java.util.Arrays;

public class 삽입정렬 {
	public static void main(String[] args) {
		int[] arr = {8,5,6,2,4};
		
		for (int i = 1; i < arr.length; i++) {
			for (int j = i; j > 0; j--) {
			
				if(arr[j-1] > arr[j]) {
					int temp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = temp;
				}
			}
			
			
		}
		System.out.println(Arrays.toString(arr));
	}
}