[Algorithm] JAVA 정렬 알고리즘 - 삽입정렬(Insertion Sort)

 

ㅇ 삽입 정렬 (Insertion Sort)

정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하여 정렬하는 방식이다. 평균 시간복잡도는 O(n²)로 느린 편이지만 구현하기 쉽다.

 

 

 

 

 

ㅇ 삽입 정렬의 이해

삽입 정렬의 과정은 다음과 같다.

① index 1의 데이터를 선택한다.

② 선택 인덱스(index 1)의 데이터와 이전 정렬된 데이터 범위의 데이터를 비교하여 삽입될 위치를 찾는다.

③ 삽입 위치에 데이터를 삽입한다.

④ index 1에서 index 2로 변경한다.

 

위 과정을 반복하며 정렬한다.

 

5 4 1 3 2 라는 배열을 초기 상태를 두고 그림으로 표현하면 다음과 같다.

 

 

index 1에 해당하는 숫자를 선택하여 정렬된 데이터 범위 내의 어디에 삽입 될 것인지 찾는다.

적절한 위치를 찾으면 데이터를 뒤로 미루고, 미룬 자리에 선택된 데이터를 삽입한다.

 

 

 

출처 : 위키백과 삽입 정렬

 

 

 

 

ㅇ 삽입 정렬 자바 코드

class Main {
    public static int[] arr = new int[5];

    public static void main(String[] args) {

        arr = new int[]{5, 4, 1, 3, 2};

        insertionSort(arr);
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " " );
        }
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 선택 데이터
            int key = arr[i];
            //비교 데이터
            int j = i - 1;

            // 이전의 원소가 더 크다면 데이터는 하나씩 밀려난다.
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

먼저 arr을 5 4 1 3 2라는 정렬되지 않은 배열로 초기화한 후, insertionSort(arr)을 수행한다.

insertionSort은 삽입 정렬을 한다.

삽입 정렬은 index 1부터 시작하기 때문에 1부터 배열 크기만큼 정렬한다.

먼저 key에는 선택 데이터(index 1)가 들어있고, j는 정렬된 데이터 범위이다.

선택 데이터가 정렬된 데이터 중 한 데이터보다 작다면 원소는 뒤로 밀려난다.

 

 

 

 

 

 

---

 

 

 

 

 

ㅇ 삽입 정렬 정리

 

1. 안정 정렬(Stable Sort)이다. 

• 같은 값을 가지는 원소의 순서가 정렬 전과 동일하게 유지된다.

 

2. 제자리 정렬(In-Place Sort)이다.

• 입력 배열 내에서 정렬이 수행되므로, 별도의 추가 메모리가 필요하지 않는다.

 

3. 데이터가 거의 정렬되어 있을 때는 효율적이다.

• 입력 배열이 이미 정렬되어 있는 경우, 삽입 정렬은 더 빠르게 수행되지만 역순으로 정렬되어 있을 경우, 최악의 시간복잡도 O(n²)를 가진다.