Insertion Sort(삽입 정렬)

Insertion sort 란?

삽입 정렬은 정렬되지 않은 리스트를 순차적으로 이미 정렬된 배열의 적절한 위치에 삽입하여 정렬을 완성하는 방식입니다. 이 알고리즘은 부분적으로 정렬된 배열을 유지하며, 각 반복에서 하나의 원소를 정렬된 배열 부분으로 이동시킵니다.

 

Insertion sort 사이클 설명

삽입 정렬의 한 사이클은 다음과 같이 진행됩니다:

1. 배열의 두 번째 요소를 선택합니다(첫 번째 요소는 이미 정렬된 상태로 간주).
2. 선택된 요소를 그 이전의 요소들과 비교하여 적절한 위치를 찾습니다.
3. 선택된 요소가 이전 요소보다 크면 그 위치에 삽입됩니다.
4. 배열의 모든 요소가 이 과정을 거쳐 정렬될 때까지 반복합니다.

이 사이클은 배열의 각 요소가 올바른 위치에 있을 때까지 계속됩니다.

 

Insertion sort 시간복잡도와 공간복잡도

• 시간 복잡도:
  • 최선의 경우(Best Case): 𝑂(𝑛) - 이미 정렬된 배열을 다룰 때
  • 평균 및 최악의 경우(Worst Case): 𝑂(𝑛2) - 역순으로 정렬된 배열을 다룰 때 또는 무작위 배열
• 공간 복잡도: 𝑂(1)O(1) - 삽입 정렬은 추가적인 저장 공간을 필요로 하지 않으며, 인플레이스 정렬 방식입니다.

 

Insertion sort 의 장단점

장점:

• 단순하고 직관적: 이해하고 구현하기 쉽습니다.
• 인플레이스 정렬: 추가적인 메모리를 요구하지 않습니다.
• 안정 정렬: 동일한 값을 가진 요소의 상대적 순서가 유지됩니다.
• 부분적으로 정렬된 배열에 효율적: 이미 정렬된 데이터에 대해 매우 빠릅니다.

단점:

• 비효율적인 시간 복잡도: 큰 데이터 세트에 대해 𝑂(𝑛2)의 시간 복잡도를 가집니다.
• 비교 및 이동 횟수: 평균적으로 많은 비교와 이동이 필요합니다.

 

Insertion sort 코드

golang

package main

import "fmt"

// InsertionSort 함수는 삽입 정렬을 구현한다.
func InsertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        // key보다 큰 arr[j]를 한 위치 뒤로 이동
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j = j - 1
        }
        arr[j+1] = key
    }
}

func main() {
    arr := []int{12, 11, 13, 5, 6}
    InsertionSort(arr)
    fmt.Println("Sorted array is:", arr)
}

 

java

public class InsertionSort {
    /* 삽입 정렬을 수행하는 함수 */
    void sort(int arr[]) {
        int n = arr.length;
        for (int i=1; i<n; ++i) {
            int key = arr[i];
            int j = i-1;

            /* key보다 큰 arr[j]를 한 위치 뒤로 이동 */
            while (j>=0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = key;
        }
    }

    // 메인 메소드로 실행
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6};
        
        InsertionSort ob = new InsertionSort();
        ob.sort(arr);
        
        System.out.println("Sorted array");
        for (int i=0; i<arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

 

python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 예제 배열
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array is:", arr)

 

sort