[기초] C++ 알고리즘 : 삽입 정렬 (Insertion Sort)

---

 

삽입 정렬은 매우 직관적이고 구현이 간단한 정렬 알고리즘입니다.

기본 원리는 이미 정렬된 배열의 부분에 새로운 원소를 그에 맞는 위치에 삽입하는 방식으로 진행됩니다.

이 때문에 삽입 정렬은 거의 정렬된 데이터에 대해 매우 효율적입니다.

최선의 경우 O(n)의 시간 복잡도를 보이며, 평균과 최악의 경우 O(n^2)입니다.

 

---

 

#include <iostream>
using namespace std;

// 배열을 출력하는 함수
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void insertionSort(int arr[], int n) {
    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--;
        }
        arr[j + 1] = key;  // key를 올바른 위치에 삽입
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "정렬 전 배열: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "정렬 후 배열: ";
    printArray(arr, n);

    return 0;
}

 

이 코드는 C++로 작성된 삽입 정렬 알고리즘 예제입니다.

삽입 정렬은 배열을 정렬하는 간단한 방법 중 하나입니다.

위 코드는 정수 배열을 오름차순으로 정렬합니다.

'insertionSort' 함수는 삽입 정렬 알고리즘을 구현하고,

'printArray' 함수는 배열의 내용을 출력합니다.

'main' 함수에서는 예제 배열을 정의하고,

이를 정렬하고 결과를 출력합니다.

 

실행 결과는 다음과 같습니다

 

정렬 전 배열: 12 11 13 5 6 
정렬 후 배열: 5 6 11 12 13

 

 

이 예제를 통해 본 삽입 정렬의 실행 결과는 주어진 배열을 성공적으로

오름차순으로 정렬한 것을 확인할 수 있습니다.

이러한 삽입 정렬은 코드가 간결하여 알고리즘을 배우는 초심자에게 적합하며,

작은 데이터에 대해서 빠르게 작동합니다.

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀