[이코테 with Java] 삽입 정렬

삽입 정렬이란?

---

 

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬(Insertion Sort)이라고 부른다. 

더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 

삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만, 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.

삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다.

 

예를 들어 초기 데이터가 7 5 9 0 3 1 6 2 4 8로 구성되어 있다고 가정하자.

삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

7 5 9 0 3 1 6 2 4 8

 

첫 번째 데이터 '7'은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. 

'7'의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재한다. 

우리는 카드를 오름차순으로 정렬하고자 하므로 '7'의 왼쪽에 삽입한다.

5 7 9 0 3 1 6 2 4 8

 

이어서 '9'가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 '9'는 '5'와 '7'보다 크기 때문에 원래 자리 그대로 둔다.

5 7 9 0 3 1 6 2 4 8

 

이어서 '0'이 어떤 위치에 들어갈지 판단한다. '0'은 '5', '7', '9'와 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입한다.

0 5 7 9 3 1 6 2 4 8

 

이어서 '3'이 어떤 위치에 들어갈지 판단한다. '0'과 '5' 사이에 삽입한다.

0 3 5 7 9 1 6 2 4 8

 

---

이와 같이 적절한 위치에 삽입하는 과정을 N - 1번 반복하게 되면 다음과 같이 모든 데이터가 정렬된 것을 확인할 수 있다.

 

삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이 특징이다. 따라서 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 

 

따라서 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 된다.

import java.util.*;

public class Main {

    public static void main(String[] args){

        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 1; i < n; i++){
            // 인덱스 i부터 1까지 감소하며 반복하는 문법
            for(int j = i; j > 0; j--){
                // 한 칸씩 왼쪽으로 이동
                if (arr[j] < arr[j - 1]){
                    // 스와프(Swap)
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }

                // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                else break;
            }
        }

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

 

삽입 정렬의 시간 복잡도

---

삽입 정렬의 시간 복잡도는 O(N ^ 2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 

삽입 정렬은 선택 정렬과 비슷한 시간이 소요되지만, 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 따라서 최선의 경우 O(N)의 복잡도를 가진다. 

 

그러므로, 거의 정렬되어 있는 상태라면 삽입 정렬을 이용하는 것이 좋다.