InsetionSort(삽입정렬) - JAVA

InsetionSort의 개념을 간단하게 알아보고, java로 구현해보자.

삽입 정렬이란?

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

삽입 정렬 과정

1) 2번째 index부터 key값을 잡는다.
2) key값에서 역순으로 탐색한다.
3) key 자신보다 작은 값을 찾거나 첫번째 index에 도달하면
그 값과 swap 한다.

[3,7,2,5,1,4] 리스트를 InsetionSort로 정렬해보자.

• 2번째 index부터 key값을 설정하고, 역순으로 정렬 된 배열을 탐색하며 key 자신보다 큰 값을 뒤로 밀어준다.
• key 자신보다 작거나 첫 index에 도달했을 때 key 값을 그 위치에 삽입한다.
• 항상 1번째 index는 정렬이되어있다고 가정한다.

시간복잡도(Time Complexity)

• best : O(N)

이동없이 1번의 루프만을 돈다.

• worst : O(N^2)

각 루프마다 매번 이동이 발생할 때, 시간복잡도는 항상 O(N^2)이다.

구현

public class insertionSort {
    static void insertionSort(int[] list){
        int i=0,j=0,key=0;
        for(i=1;i<list.length;i++){
            key=list[i];
            for(j=i-1;j>=0 && list[j]>key;j--){
                list[j+1]=list[j];
            }
            list[j+1]=key;
        }
    }

    public static void main(String[] args){
        int[] list={3,7,2,5,1,4};
        insertionSort(list);
        for(int i=0;i<list.length;i++){
            System.out.print(list[i]+",");
        }
    }
}

Reference

• 삽입정렬 - 위키백과