[C++로 배우는 알고리즘과 자료구조] Day 17: 삽입 정렬과 쉘 정렬

삽입 정렬 (Insertion Sort)

삽입 정렬은 배열의 요소를 하나씩 정렬된 부분에 삽입하는 방식으로 동작합니다. 각 요소를 적절한 위치에 삽입하기 위해 이미 정렬된 부분을 오른쪽으로 이동시킵니다.

삽입 정렬의 시간 복잡도:

• 최선의 경우: (O(n))
• 평균의 경우: (O(n^2))
• 최악의 경우: (O(n^2))

삽입 정렬 구현

#include <iostream>
#include <vector>

// 삽입 정렬 함수
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    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;
        }
        arr[j + 1] = key; // 키를 정렬된 부분에 삽입
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};

    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    insertionSort(arr);

    std::cout << "정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

쉘 정렬 (Shell Sort)

쉘 정렬은 삽입 정렬의 일반화된 버전으로, 일정한 간격(gap)을 두고 배열을 부분적으로 정렬합니다. 간격을 점차 줄여가며 정렬을 반복하여 최종적으로 전체 배열을 정렬합니다.

쉘 정렬의 시간 복잡도:

• 평균의 경우: (O(n^{1.5}))
• 최악의 경우: (O(n^2)) (간격을 어떻게 선택하느냐에 따라 다름)

쉘 정렬 구현

#include <iostream>
#include <vector>

// 쉘 정렬 함수
void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    std::vector<int> arr = {12, 34, 54, 2, 3};

    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    shellSort(arr);

    std::cout << "정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

설명

1. 삽입 정렬 (Insertion Sort):
   • 배열의 요소를 하나씩 정렬된 부분에 삽입합니다.
   • 최선의 경우 시간 복잡도는 (O(n))이고, 평균 및 최악의 경우 시간 복잡도는 (O(n^2))입니다.
2. 쉘 정렬 (Shell Sort):
   • 일정한 간격(gap)을 두고 배열을 부분적으로 정렬하며, 간격을 점차 줄여가며 정렬을 반복합니다.
   • 시간 복잡도는 간격을 어떻게 선택하느냐에 따라 다르지만, 평균적으로 (O(n^{1.5}))입니다.

이제 삽입 정렬과 쉘 정렬의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 정렬 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 18: 합병 정렬"에 대해 학습하겠습니다.