삽입정렬 코드 실행

삽입정렬 코드 작성 후 디버깅표를 만들어보자.

package day006;

public class sortedarray {
	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;

		for (int i = 1; i < arr.length; i++) {
			int pivot = arr[i]; // 기준값
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j] > pivot) {
					arr[j + 1] = arr[j];
					arr[j] = pivot;
				}
			}
		}
		for (int datas : arr) {
			System.out.print(datas + " ");
		}
	}
}

 

디버깅 표

4회전 후에 정렬이 완료된다!

삽입정렬은 안정정렬인데 안전정렬 이라는 뜻은 중복된 값이 있을때 서로의 위치가 바뀌지 않는 정렬이다.

정렬에 따라 같은 값이더라도 자리가 바뀔 수 있다.

 

언뜻보면 삽입정렬은 버블정렬의 반대형태를 띄우는 것 같다. 하지만 교환이 이루어지는 버블정렬과 달리 삽입정렬은 

추가적인 temporary 공간을 생성 할 필요없이 정렬이 가능하다.

 

버블정렬 : 일단 제일 앞 녀석 데리고 뒤로 가는 것이다. 차례로 비교해나가다가, 더 큰 녀석이 있으면 더 큰 녀석을 뒤로 데리고 간다. 그러면 제일 뒤에는 제일 큰 녀석이 서겠죠. 이런 식으로 계속 하면 정렬이 되며 비교를하고 바꿀때마다 temp공간을 만들어 교환을 해준다.

삽입정렬 : 처음부터 pivot까지 봐서, 제일 작은 녀석을 제일 앞 자리와 바꾼다. 두번째로 볼 때는 나머지에서 가장 작은 사람과 두 번째 녀석이랑 바꾸는식으로 해서 가장 작은숫자가 앞으로 오게된다. 새로운공간을 만들어 교환하는것이 아닌 pivot부터 처음까지 쭈우욱 비교해보다가 pivot이 들어갈 위치가 맞으면 삽입! -> temp공간 필요하지 않다.