[알고리즘] 삽입 정렬 - C++

삽입 정렬

---

#include <iostream>

using namespace std;

int arr[] = {4, 2, 6, 1, 5, 3};

int main()
{
    for (int i = 1; i < 6; i++){
        int j = i;
       
        while (j >= 0 && arr[j - 1] > arr[j]){	//왼쪽에 있는 값이 오른쪽에 있는 값보다 큰 경우 계속 swap
            int temp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = temp;
            j--;
        }
    }

    for (int i=0; i < 6; i++)
        cout << arr[i] << ' ';

    return 0;
}

시간복잡도: O(N^2)