[Algorithm] Sorting / Insertion Sort

Insertion Sort(삽입 정렬)

삽입 정렬 알고리즘이란?

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
• 즉, 삽입 정렬을 두 번째 자료부터 시작하여 그 앞 왼쪽의 자료들과 비교하여 삽입할 위치를 지정한 후, 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입합니다.
• 앞에 있는 원소들이 이미 정렬되어있다고 가정합니다.

버블 정렬의 코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int main(){
    int a[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    int n = 10;

    for(int i=1; i<n; i++){
        for(int j=i-1; j>=0; j--){
            if(a[j]<a[j+1]) break;
            if(a[j]>a[j+1]){
                swap(a[j], a[j+1]);
            }
        }
    }
    
    for(int i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
}

#include <iostream>
using namespace std;

int main(){
    int a[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    int n = 10;

    for(int i=1; i<n; i++){
        int j = i-1;
        while(j>=0 && a[j]>a[j+1]){
            swap(a[j], a[j+1]);
            j--;
        }
    }
    
    for(int i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
}

두 가지 코드로 구현해보았습니다! 원리는 동일합니다 ㅎㅎ

삽입 정렬의 시간복잡도

• 평균: O(n^2)
• 단, 데이터가 이미 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다는 특징을 갖고있습니다. 이 경우에는, 이동없이 1번의 비교만 이루어집니다. -> O(n)