정렬 알고리즘 - 삽입 정렬 (Insertion sort)

 

삽입 정렬 (Insertion sort) 이란?

 

 

삽입정렬은 리스트를 정렬하는 과정에서 이미 정렬된 부분 리스트와 비교하여 각 요소를 그 위치에 삽입하는 알고리즘입니다. 이 과정에서 삽입정렬은 각 요소를 정렬된 부분 리스트에 "적절한 위치에 삽입"하는 방식으로 동작하며, 이러한 특성에서 알고리즘의 이름이 지어졌습니다.

 

삽입 정렬은 아래와 같은 과정을 따릅니다.

1. 리스트의 두 번째 요소부터 시작하여 이미 정렬된 부분 리스트와 비교합니다.
2. 적절한 위치를 찾을 때까지 이전 요소와 비교하며 이동합니다.
3. 비교하고자 하는 요소보다 작거나 같은 값을 가진 요소를 찾으면, 해당 요소 바로 뒤에 삽입합니다.
4. 이러한 과정을 반복하여 전체 리스트가 정렬될 때까지 진행합니다.

 

 

삽입 정렬 코드 예시 (C#)

 

아래 코드는 C#으로 작성된 버블 정렬 알고리즘의 예시입니다. 입력된 배열 {64, 34, 25, 12, 22, 11, 90}을 삽입 정렬 알고리즘을 사용하여 오름차순으로 정렬한 결과를 출력합니다.

 

using System;

class InsertionSort {
    static void Insertion_Sort(int[] arr) {
        int n = arr.Length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;

            // Print intermediate result
            Console.Write("Iteration " + i + ": ");
            foreach (int num in arr) {
                Console.Write(num + " ");
            }
            Console.WriteLine();
        }
    }

    static void Main() {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        Console.WriteLine("Original array:");
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
        Console.WriteLine();

        Insertion_Sort(arr);

        Console.WriteLine("\nSorted array:");
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
    }
}

 

위 코드를 실행한 결과는 다음과 같습니다.

 

Original array:
64 34 25 12 22 11 90 
Iteration 1: 34 64 25 12 22 11 90 
Iteration 2: 25 34 64 12 22 11 90 
Iteration 3: 12 25 34 64 22 11 90 
Iteration 4: 12 22 25 34 64 11 90 
Iteration 5: 11 12 22 25 34 64 90 
Iteration 6: 11 12 22 25 34 64 90 

Sorted array:
11 12 22 25 34 64 90

 

 

삽입 정렬 장단점

 

- 장점

• 구현이 간단하고 이해하기 쉽습니다.
• 이미 거의 정렬된 리스트에 대해서는 빠르게 동작합니다.
• 안정적인 정렬 방법입니다.

- 단점

• 평균 및 최악의 경우에는 시간 복잡도가 O(n^2)으로 비효율적일 수 있습니다.
• 다른 정렬 알고리즘에 비해 성능이 낮을 수 있습니다.

 

삽입 정렬 사용 사례

 

• 리스트의 크기가 작거나 거의 정렬된 경우에 적합합니다.
• 데이터의 수가 적고, 추가적인 메모리 공간을 사용하기 어려운 경우에 삽입정렬을 사용할 수 있습니다.

 

삽입정렬은 간단하면서도 구현하기 쉬운 정렬 알고리즘 중 하나로, 작은 크기의 리스트를 정렬하는 데에 효과적입니다. 이미 정렬된 리스트에 대해서는 성능이 우수하며, 리스트의 크기가 작을수록 효율적으로 동작합니다. 그러나 리스트의 크기가 커지거나 데이터의 정렬 상태에 따라 성능이 저하되는 경우가 있습니다. 따라서 정렬해야 할 데이터의 크기와 정렬 상태를 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요합니다.