[Algorithm] Insertion Sort

Insertion Sort

삽입정렬은 Stable한 정렬로 1번째 인덱스부터 시작해 N번째 인덱스까지 반복하며 자신이 삽입될 위치를 찾아 스왑한다
평균 O(N^2)의 시간복잡도와 O(1)의 공간 복잡도를 가지게 되며 코드가 단순해 구현이 간단하다
최선의 시간 복잡도는 O(N)이다
어느정도 정렬된 배열에 대해선 속도가 우수하다
적은 크기의 배열의 정렬(엔티티 2^5~2^6개) 에 대해서 속도가 우수하다

동작 원리

오름차순 정렬 기준

1번째 인덱스부터 시작한다
앞 인덱스의 값이 자신보다 작을때 까지 스왑한다
다시 1번으로 돌아가 N-1번째 인덱스까지 반복한다

구현

c++

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <random>
#include <numeric>

using namespace std;

void InsertionSort(vector<int> &insertionSortvec){
    int MAXSIZE = insertionSortvec.size();
    for(int start = 1; start < MAXSIZE; ++start){
        for(int compare = start-1; compare >= 0 && insertionSortvec[compare] > insertionSortvec[compare+1]; --compare){
            insertionSortvec[compare] ^= insertionSortvec[compare+1] ^= insertionSortvec[compare] ^= insertionSortvec[compare+1];
        }
    }
}

int main() {
    std::srand ( unsigned ( std::time(0) ) );
    vector<int> vec(1000);
    iota(begin(vec),end(vec),1);
    std::shuffle(std::begin(vec), std::end(vec), default_random_engine {});
    cout<<"Before Selection Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    cout<<endl;

    InsertionSort(vec);

    cout<<"After Selection Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    return 0;
}

Insertion Sort

동작 원리

구현

같이보기