알고리즘-삽입정렬

다양한 정렬의 방법중 앞서 포스팅 한 선택정렬과 또 다른 정렬방법입니다.
잠깐 복습하자면,
선택정렬은 맨 앞 즉 왼쪽부터 정렬되지 않은 배열중 가장 작은 값의 위치를 서로 바꾸어,
왼쪽부터 가장 작은 값들로 채워져 정렬되는 방법입니다.
삽입정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.
선택정렬에 비해 구현난이도가 더 높은 편이지만, 일반적으로 더 효율적으로 동작합니다.

삽입 정렬의 시간 복잡도

• 삽입정렬의 시간 복잡도는 O(N^2)입니다. 선택정렬과 동일하게 반복문이 중첩되어 사용됩니다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면, 매우 빠르게 동작합니다.
• 최선의 경우 O(N)의 시간 복잡도를 가집니다.
  ->이미 정렬된 경우 위치 변동이 없기 때문에 N번의 수행만으로 종료가 됩니다.

#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;

int target[10]={9,2,3,5,6,7,1,4,8,10};
int n=10;

int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j>0;j--){
            if(target[j]<target[j-1]){
                swap(target[j],target[j-1]);
            }
            else{
                break;
            }
        }
    }
    
    for(int i=0;i<n;i++){
        cout<<target[i]<<' '<<"\n";
    }
    
    
    
    
    
    return 0;
}

삽입 정렬을 구현한 코드입니다.
작성한 코드중 이해가 안되는 부분이 있다면 ,댓글로 남겨주세요!
이해를 위한 그림은 추후에 추가하도록 하겠습니다!