자바 삽입정렬

자바 삽입정렬

 

삽입정렬이란?

15

11

1

3

8

위와 같이 5자리 인덱스가 있다면 2번째에 있는 숫자를 픽해서 앞에숫자와 픽한 숫자와 자리 비교를 하면서 큰 수를 뒤로 보내는것이다. 아래는 예를 보면서 이해하면 편할듯싶다.

 

1회전 

픽 : 11 (2번째 자리)

15 11 1 3 8 

>>> 15가 11보다 더 크므로 자리 바뀜

11 15 1 3 8 

 

2회전

픽 : 1 (3번째 자리)

11 15 1 3 8

>>> 11이 1보다 크므로 자리 바뀜

1 15 11 3 8

 

픽 : 11 (3번째 자리)

1 15 11 3 8

>>> 15가 11보다 크므로 자리 바뀜

1 11 15 3 8

 

3회전

픽 : 3 (4번째 자리)

1 11 15 3 8

>>> 3이 1보다 크므로 자리바뀌지 않음

1 11 15 3 8

 

픽 : 3 (4번째 자리)

1 11 15 3 8

>>> 11이 3보다 크므로 자리바뀜

1 3 15 11 8

 

픽 : 11 (4번째 자리)

1 3 15 11 8

>>> 15가 11보다 크므로 자리 바뀜

1 3 11 15 8

 

4회전

픽 : 8 (5번째 자리)

1 3 11 15 8

>>> 1이 8보다 작으므로 자리바뀜 없음

1 3 11 15 8

 

픽 : 8 (5번째 자리)

1 3 11 15 8

>>> 3이 8보다 작으므로 자리 바뀜 없음

1 3 11 15 8

 

픽 : 8 (5번째 자리)

1 3 11 15 8

>>> 11이 8보다 크므로 자리바뀜

1 3 8 15 11

 

픽 : 11 (5번째 자리)

1 3 8 15 11

>>> 15가 11보다 크므로 자리 바뀜

1 3 8 11 15

 

비교횟수 : n(n-1)/2

 

시간복잡도(빅오표기법)

최상	평균	최악
O(n)	O(n^2)	O(n^2)

 

삽입정렬 소스

/*
삽입정렬
 */
package algorithm;

public class InsertionSort {
    public static void main(String[] args){
        int arr[] = {5, 2, 3, 4, 1};

        System.out.println("인덱스 배열");
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + "");
        System.out.println("");
        System.out.println("정렬 시작");

        int tmp;
        int a, b;
        for(a =1 ; a <arr.length; a++){
            tmp = arr[a];
            for(b = a -1; b >=0; b--){
                if(arr[b] > tmp ){
                    arr[b+1] = arr[b];
                } else{
                    break;
                }
            }
            arr[b+1] = tmp;
            for(int k = 0; k<arr.length; k++)
                System.out.print(arr[k]+" ");
            System.out.println("");

        }

        System.out.println("정렬 끝");
        for(int k = 0; k<arr.length; k++)
            System.out.print(arr[k]+" ");

    }
}