삽입 정렬(Insertion Sort)

시간복잡도

O(n^2)

// 선택된 수를 정렬된 위치 사이에 
void insertionSort(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int key = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] > key)
                arr[j + 1] = arr[j];
            else
                break;
        }
        arr[j + 1] = key; // 찾은 위치에 삽입 
    }
    cout << "========== insertion sort ==========" << endl;
}