[Data Structure] 삽입 정렬 - Insertion Sort

삽입 정렬 (Insertion Sort)

Stable Sort

 

시간복잡도

- 최선 : O(n)

- 평균/최악 : O(n²)

 

장점

- 레코드 수가 적을 경우, 알고리즘이 매우 간단하다

- 정렬이 대부분 되어있는 리스트의 경우 매우 효율적

 

단점

- 많은 레코드들이 이동행한다

- 레코드 수가 많고 레코드 크기가 크면 적합하지 않다

 

과정

• 리스트의 2번째 요소부터 인덱스를 내려가면서 비교해서 정렬

 

▶ Insertion Sort Code

static void insertion_sort(int [] list){
        Calendar before = Calendar.getInstance();
        for(int i=1; i<list.length; i++){
            int key = list[i]; // i번째 요소
            int index = i-1; // 비교 = i번째 밑에 있는 요소들
            while(index>=0 && list[index] > key) {
                // 밑에 있는 요소들이 key보다 크면
                list[index + 1] = list[index];
                // 해당 요소를 오른쪽으로 밀기
                index--;
            }
            list[index+1] = key;
            // key보다 큰 요소들을 다 오른쪽으로 밀어버리고 해당 공간에 key 삽입
        }
    }

 

▶ Full Code

package Sort;

import java.util.Calendar;

public class Insertion_Sort_9 {
    public static void main(String[] args) {
        int [] A = new int[30]; // 정렬할 배열 A

        for(int i=0; i<A.length; i++)
            A[i] = (int)(Math.random()*201); // 0~200

        // 정렬 전 A 출력
        System.out.print("A []");
        for(int i=0; i<A.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println("\n");

        insertion_sort(A);
    }

    static void insertion_sort(int [] list){
        Calendar before = Calendar.getInstance();
        for(int i=1; i<list.length; i++){
            int key = list[i]; // i번째 요소
            int index = i-1; // 비교 = i번째 밑에 있는 요소들
            while(index>=0 && list[index] > key) {
                // 밑에 있는 요소들이 key보다 크면
                list[index + 1] = list[index];
                // 해당 요소를 오른쪽으로 밀기
                index--;
            }
            list[index+1] = key;
            // key보다 큰 요소들을 다 오른쪽으로 밀어버리고 해당 공간에 key 삽입
        }
        Calendar after = Calendar.getInstance();

        // 정렬 후 A 출력
        System.out.print("result []");
        for(int i=0; i<list.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(list[i] + "\t");
        }
        System.out.println("\n");

        int time = after.get(Calendar.MILLISECOND) - before.get(Calendar.MILLISECOND);
        System.out.println("걸린 시간 : " + time + "ms");
    }
}