자바로 구현한 삽입 정렬 알고리즘

삽입 정렬은 Target 인덱스를 정해서 올바른 인덱스에 삽입해 주는 정렬 방식입니다.

삽입 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다.

 

1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다.

2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다.

3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다.

 

 

선택정렬의 정렬 과정을 요약하면 다음과 같습니다.

1. 첫 인덱스와 이미 정렬된 인덱스를 제외한 가장 작은 인덱스를 타깃으로 결정합니다.

2. 타겟과 타깃보다 작은 인덱스의 값들을 비교하여 정렬합니다.

3. 모든 인덱스가 정렬될 때까지 1,2번 과정을 반복합니다.

 

그림으로 보겠습니다.

그림으로 보시게 되면 큰 어려움 없이 이해할 수 있게 될 것입니다.

 

다음은 자바로 삽입 정렬을 구현해 보겠습니다.

public class insert_sort {
    public static void main(String[] args) {
        int[] array = new int[10];

        //배열에 난수 저장
        for(int i=0; i<array.length; i++){
            array[i] = (int)(Math.random()*100);
        }

        //정렬전 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }

        //삽입 정렬
        insert_sort(array);

        System.out.println();
        System.out.println();

        //정렬후 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }
    }

    public static void insert_sort(int[] array){
        //타겟을 i로 잡고 인덱스를 하나씩 늘려갑니다.
        for(int i=1; i<array.length; i++){
            int target = array[i];
            //타겟보다 전 인덱스를 비교합니다.
            int j = i-1;
            while(j>=0&&array[j]>target){
                array[j+1] = array[j];//해당 값을 오른쪽으로 민다.
                j--;
            }

            array[j+1] = target;
        }
    }

}

 

중요한 부분은 insert_sort 부분인데 위에 그림과 알고리즘과 살짝 차이가 있습니다.

한 부분만 그림으로 설명드리면

다음과 같이 코드가 돌아갑니다.

 

선택정렬의 장단점입니다.

 

장점

1. 메모리가 추가적으로 필요하지 않다.

2. 거의 정렬된 상태에서 효율적인 정렬 방식이다. 최선의 경우 O(N)의 시간복잡도를 가진다.

3. 안전정렬이 가능하다.

 

단점

1. 역순의 가까울수록 비효율적이다. 최악의 경우 O(N²)의 시간복잡도를 가진다.

2. 데이터의 상태에 따라 성능편차가 매우 심하다.