[JAVA] 자바 정렬 : 삽입 정렬 (insertion sort)

삽입 정렬 : 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식. 

 

방법

두 번째 숫자를 첫 번째랑 비교하여 큰 값이랑 자리를 바꾸고 세 번째 값을 첫 번째, 두 번째 값과 비교하여 자리를 바꾸고 나머지를 그대로 밀어버리고 반복해서 비교 한다. 

 

	int arr [] = {3,6,1,2,8}; //배열 선언 한 후 
		int i,j; //변수도 선언 
		
		
		for(i=1;i<arr.length;i++) { //배열의 길이 만큼 돌꺼다
			int tmp = arr[i]; 
            //정렬들을 뒤로 미루다가 기존 값이 지워 질 수 있으니 tmp에 먼저 값을 담아놓고
			j=i-1; 
						
			//자리 잡을 값 (tmp) 보다 큰 값들을 만나면 뒤로 한칸 씩 이동 한다. 
			while (j>=0 && tmp <arr[j]) { //while(조건) = 조건이 충족하지 않을 떄까지 수행 
				arr[j+1] = arr[j]; //뒤로 미루고 
				j--; //tmp와 비교할 값을 한칸씩 앞으로 이동 
			}
			j++;
			arr[j]=tmp; //자기 자리에 tmp값 삽입 
		}
		System.out.println("정렬 후");
		for (i = 0; i < arr.length; i++) {
			System.out.println(arr[i] + "\t");
		}

arr 배열에 생성 된 숫자들을 삽입 정렬 할 것이다.

 

우선 i 는 전체적인 반복 횟수이고, j 는 비교 하면서 반복하는 값이다. i 는 1일때 부터 시작하는데 그 이유는 삽입 정렬은 두 번째 숫자를 기준으로 비교를 시작하기 때문이다.  tmp 에는 i 의 값을 담아 두는데 그 이유는 정렬일 될 때 뒤로 한칸씩 밀려나는 현상으로 인해 내용이 삭제 될 수 있기 때문이다.

j 의 값은 i - 1 (즉, 0 부터 시작한다) 이렇게 써 준 이유는 2번째 값을 1번째와 비교하고, 3번째를 2번과 1번과 이렇게 자신보다 앞에 있는 숫자들과 비교해서 진행하기 때문이다. 

while 은 조건이 충족하지 않을 때까지 수행 한다.  조건에 만족하였다면, 위치를 바꿔줘야 함으로 arr[ j+1 ] = arr[ j ]; 이걸 진행 한 것이다. while 조건에 충족하지 않았다면 j 의 데이터가 작다는 뜻임으로 자기 자신의 자리를 tmp 로 지정한다. 

반복후 프린트 하면 완성.