[배열] 삽입 정렬 (Insertion sort)

삽입 정렬이란?

삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

---

코드

package solo1;

public class Insertsort {
	public static void main(String[] args) {
		int[] arr = new int[5];

		arr[0] = 100;
		arr[1] = 5;
		arr[2] = 60;
		arr[3] = 1000;
		arr[4] = 30;

		// [100,5,60,1000,30]

		for (int i = 1; i < arr.length; i++) {
			int key = arr[i]; // 기준값
			for (int j = i - 1; j > -1; j--) {
				if (arr[j] > key) {
					arr[j + 1] = arr[j];
					arr[j] = key;

				}

			}
			for (int a : arr) {
				System.out.print(" " + a);
			}
			System.out.println();
		}

	}

}

---

디버깅표

i	i<length	key	j	j > -1	arr[j]>key	arr[j+1]	arr[j]
1	1<5 T	5	0	0>-1 T	100>5 T	100	5
			-1	-1>-1 F
2	2<5 T	60	1	1>-1 T	100>60 T	100	60
			0	0>-1 T	5 > 60 F
				-1>-1 F
				●
				●
				●
5	5<5 F

---

결과

5 100 60 1000 30

5 60 100 1000 30

5 60 100 1000 30

5 30 60 100 1000

---