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

📚 삽입 정렬이란?

삽입 정렬은 작은 데이터 집합에 효율적인 알고리즘이다. 카드 정렬과 유사한 방식으로 작동하는 정렬 알고리즘이다. 손에 들고 있는 카드를 하나씩 차례대로 정렬된 위치에 삽입하는 듯, 삽입 정렬은 리스트를 순차적으로 정렬된 부분과 비교하여 알맞은 위치에 데이터를 삽입한다.이 과정을 반복하는 것이다.

 

1️⃣ 삽입 정렬의 구체적 과정

 

 

2️⃣ 시간 복잡도 비교

 

3️⃣ Java로 알아보는 삽입 정렬

public class Main {
    public static void insertion (int[] data) {
        for (int i = 0 ; i < data.length ; i++) {
            int key = data[i];
            int j = i - 1;

            while (j >= 0 && data[j] > key) {
                data[j+1] = data[j];
                j = j - 1;
            }
            data[j+1] = key;
        }
    }

    public static void main(String[] args) {
        int[] sort = {5, 2, 9, 1, 5, 6};

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

4️⃣ Python으로 알아보는 삽입 정렬

data = [5, 2, 9, 1, 5, 6]

def insertion(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1

        arr[j+1] = key

insertion(data)

print(data)