[프로그래밍] JAVA자바연습 insert삽입정렬

 

 삽입정렬을 만들어보기.

39부터 200미만의 난수를 복원추출하여
크기가 30인 배열에 담고
해당 배열을 삽입정렬로 오름차순 정렬하는 문제.

삽입 정렬

 

삽입정렬은 배열에서
2번째 값부터 마지막 값까지 추출하여 검토한다.
1회차: 2번째 값을 꺼내서 1번째 값과 비교
2회차: 3번째 값을 꺼내서 1,2번째 값과 비교
3회차: 4번째 값을 꺼내서 1,2,3번째 값과 비교
하는 것.

오름차순일 경우
추출한 값을 앞의 값들과 비교하고, 본인보다 큰 값을 만나면
그 값부터 본인 이전의 값을 한 칸씩 뒤로 미루고
본인이 그 값의 자리로 삽입되는 방식이다.

package com.javaprac;
 
import java.util.Arrays;
 
public class InsertSort {
 
    public static void main(String[] args) {
        
        int[] randomArray = new int[30];
        int changeCount = 0;
        for(int i =0; i<30; i++) {
            randomArray[i]= (int)(Math.random()*161)+39;            
        }
        System.out.println("랜덤배열->");
        System.out.println(Arrays.toString(randomArray));
        
        
        
        for(int j=1; j<30; j++) {    
            for(int k=0;k<=j-1;k++) {
                if(randomArray[j]<randomArray[k]) {
                    int temp = randomArray[j];
                    for(int n=j-1; n>k;n--) {
                        randomArray[n+1]= randomArray[n];                    
                        changeCount++;
                        System.out.println(n+"번째 값이"+(n+1)+"번째로 이동합니다요.");
                    }
                    randomArray[k]=temp;
                    
                }
                
                
            }
            
        }
        System.out.println("->삽입정렬");
        System.out.println(Arrays.toString(randomArray));
        System.out.println("자리바꿈의 횟수"+changeCount);
        
        
        
    }
 
}
 

1:본인의 eclipse 자바 연습 패키지의 이름이다.
3: toString() 을 이용하기 위하여 java,util,Arrays를 임포트한다. toString은 반복문없이 배열을 출력하는 수단.
5-44: public접근제한자의 클래스 InsertSort
7-42: 메인 메서드
9: random값을 넣기 위한 크기 30의 int배열 randomArray를 선언한다.
10: 몇 번 체인지가 이루어졌는지 체크하기위한 int 변수 changeCount를 0으로 초기화하며 선언한다.
11-13: randomArray에 난수를 바인딩하는 for문이다.  0<=Math.random<1 이므로 문제의 조건인 39~200미만의
난수를 만들기 위하여   (0*161)+39 <= Math.random < (1*161)+39 를 해준다.
14-15: 만들어진 랜덤배열을 확인하기위한 프린트문의 모습이다.
19-35: 배열의 1번인덱스(두번째값)부터 29번인덱스(마지막값)을 가져오기 위한 for문이다.
20-33: 배열의 0번인덱스(첫번째값)부터 j-1번째 값을 가져오기 위한 for문이다.
j가 10일경우 20-33for문은 0부터 j-1까지의 값을 순서대로 가져온다.
21-30: randomArray[j] 값이 randomArray[k]값보다 작다면, 
22: randomArray[j]값을 k번째로 삽입하기 위하여 temp int형 변수에 바인딩해둔다.
23-27: k번째 값부터 j-1번째 값까지는 한자리씩 뒤로 밀어내야한다. 역순으로 한 자리씩 밀어내기위하여 n--를 사용한다. 현재 체크중인 j번째값의 자리에 j-1번째 값을 넣고, j-1번째 자리에 j-2번째 값을 넣는다. k는 temp(j번째값)이
들어갈 자리이므로 k+1까지만 밀어내기 작업을 수행한다.
25: 몇 번바꿨는지 체크하기위하여 changeCount에 1을 더해준다.
26: 값이 이동할때마다 알려주는 프린트문이다. 스크롤 압박이 심하니 주석처리한다.
28: k번째 자리에 temp를 삽입한다.
36-38: 삽입 정렬 후의 randomArray의 모습을 출력한다. 자리를 몇 번 바꿨는지 출력한다.