자료구조 - 삽입 정렬

[삽입 정렬(Insertion Sort)]

삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 하나로, 리스트의 요소를 하나씩 비교하여 정렬된 부분에 적절한 위치에 삽입하는 방식입니다. 삽입 정렬은 단순하면서도 효율적인 알고리즘으로, 작은 데이터 집합이나 거의 정렬된 데이터에 대해 성능이 우수합니다.

시간 복잡도는 최악의 경우 O(n^2)입니다.

 

삽입 정렬 과정 설명

1. 리스트의 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분과 비교하여 적절한 위치에 삽입합니다.
2. 이 과정을 리스트의 마지막 요소까지 반복합니다.

 

삽입 정렬 의사 코드

함수 insertionSort(arr):
    n = 배열의 길이(arr)

    for i = 1부터 n-1까지:
        key = arr[i]
        j = i - 1

        while j >= 0 그리고 arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1

        arr[j + 1] = key

    반환 arr

 

 

삽입 정렬 예제

삽입 정렬의 과정 설명
예시 리스트: [64, 25, 12, 22, 11]

첫 번째 반복:
    두 번째 요소(25)를 선택하여 정렬된 부분([64])과 비교.
    25는 64보다 작으므로 64 앞에 삽입.
    결과: [25, 64, 12, 22, 11]

두 번째 반복:
    세 번째 요소(12)를 선택하여 정렬된 부분([25, 64])과 비교.
    12는 25보다 작으므로 25 앞에 삽입.
    결과: [12, 25, 64, 22, 11]

세 번째 반복:
    네 번째 요소(22)를 선택하여 정렬된 부분([12, 25, 64])과 비교.
    22는 25보다 작으므로 25 앞에 삽입.
    결과: [12, 22, 25, 64, 11]

네 번째 반복:
    다섯 번째 요소(11)를 선택하여 정렬된 부분([12, 22, 25, 64])과 비교.
    11은 12보다 작으므로 12 앞에 삽입.
    결과: [11, 12, 22, 25, 64]

 

 

삽입 정렬 코드

#include <iostream>
#include <vector>

using namespace std;

// 삽입 정렬 함수
void insertionSort(vector<int>& arr) 
{
    int n = arr.size();  // 배열의 길이

    for (int i = 1; i < n; i++) 
    {
        int key = arr[i];  // 현재 요소를 key로 설정
        int j = i - 1;

        // key보다 큰 요소들을 한 칸씩 뒤로 이동
        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;  // key를 올바른 위치에 삽입
    }
}

int main() 
{
    vector<int> arr = {64, 25, 12, 22, 11};  // 예제 리스트

    cout << "정렬 전: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    insertionSort(arr);  // 삽입 정렬 수행

    cout << "정렬 후: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}