Insertion Sort

Insertion sort는 sorting algorithm 중 단순한 알고리즘에 속하고, 이해하기에도 직관적이지만 그만큼 복잡도가 커지는 알고리즘입니다.
이번 글부터 기본 알고리즘에 대한 코드는 $ChatGPT$의 도움을 받아서 작성할 예정입니다.
단순하고 반복적인 알고리즘을 작성하는데 시간을 줄이기 위한 목적입니다.
예상했던것보다 $ChatGPT$가 상당히 깔끔하게 코드를 작성해주네요.

Insertion Sort Algorithm

Data가 입력으로 들어올때마다 자료구조(기본적으로 배열)의 모든 element를 비교해서 new element의 위치를 찾아내서 assign하는 알고리즘입니다.
코드를 직접 보면서 간단하게 설명하겠습니다.

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

상기 코드에서 insertionSort의 key가 new element이고, key를 arr[j]와 비교합니다.
key보다 큰 element에 대해 key의 인덱스보다 뒤로 위치할 수 있도록 assign합니다.
이를 while문에서 수행하고, key를 arr[j+1]=key;에서 할당하게 됩니다.
위으 insertionSort를 사용한 예시 main program은 아래와 같습니다.

int main() {
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Complexity Analysis

모든 element를 기존의 자료구조의 element와 비교해야하기 때문에 복잡도는 다음과 같습니다.
$T(n)=O(n^2)$