[알고리즘] 삽입 정렬(insertion sort)

삽입 정렬이란?

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

• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입한다.
• key값은 2번째 인덱스부터 시작되며, key값이 자료의 길이만큼 이동했을 때 정렬된다.

 

1) 정렬되지 않은 배열에서 2번째 인덱스를 key값으로 잡는다.

2) 앞의 인덱스와 비교하여 교환한다.

3) 2번째를 key값으로 잡았기 때문에 다음, 3번째 인덱스를 key값으로 잡는다.

4) 마찬가지로 앞의 인덱스들과 비교하여 교환한다.

시간복잡도

최선의 경우 O(n) 시간복잡도를 가지게 되지만, 최악의 경우 O(n^2)이 될 수 있다.

 

JAVA CODE

public class InsertionSort {

    public int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i], j;
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) arr[j + 1] = arr[j];
                else break;
            }
            arr[j + 1] = temp;
        }
        return arr;
    }
}