[Algorithm] 삽입 정렬(Insertion Sort)

삽입 정렬이란?

각 숫자를 적절한 위치에 삽입하는 방법이다. 필요할 때만 위치를 바꿔주는 방법이다. 각 숫자를 삽입할 위치를 살펴 볼 때, 그 숫자의 앞의 숫자들은 모두 이미 정렬된 상태이다. 따라서 필요한 만큼만 이동할 수 있기 때문에 선택정렬과 버블정렬에 비해 빠르다.

#include<stdio.h>
#include<iostream>
using namespace std;

int main(void){
    int i,j; // 반복을 위한 변수
    int temp; // 두 수의 값을 교환하기 위한 변수
    int array[10] = {1,6,9,8,2,4,10,3,7,5}; // 정렬할 배열

    // 첫 번째 수는 이미 정렬되어있다고 생각하기 때문에, 9까지 반복
    for(i=0;i<9;i++){  
        j=i; // 현재 정렬할 원소를 선택하여 적절한 위치에 삽입하기 위함
        
        // 왼쪽 수가 오른쪽 수보다 크면 자리 교체.(올바른 위치에 삽입)
        while(j>=0 && array[j] > array[j+1]){
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            j--;
        }
    }

    for(i=0;i<10;i++){
        cout<<array[i]<<endl;
    }

    return 0; 
}

시간 복잡도

최악의 경우(앞의 숫자들이 모두 정렬되지 않은 경우)는 선택 정렬, 버블 정렬과 마찬가지로 10번 + 9번 + ... + 1번으로 시간복잡도는 O(N^2)이다.

그러나 실제 연산 속도는 셋 중에서 가장 빠르다. 또한, 거의 정렬된 상태에서 삽입 정렬을 사용하면, 매우 효율적이다.

reference: https://www.youtube.com/watch?v=16I9Z7bS1iM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=4