[Algorithm] Insertion Sort(삽입 정렬)

Code

Python

def insertion_sort(a):
    for i in range(1, len(a)):
        for j in range(i, 0, -1):
            if a[j-1] > a[j]:
                a[j], a[j-1] = a[j-1], a[j]

a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3]

print(a)
insertion_sort(a)
print(a)

 

def insertion_sort2(a):
    for i in range(1, len(a)):
        j=i
        while(a[j-1]>a[j] and j!=0):
            a[j], a[j-1] = a[j-1], a[j]
            j-=1
            
a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3]

print(a)
insertion_sort(a)
print(a)

 

C++

#include <iostream>

using namespace std;

const int ARRAY_SIZE = 10;

void insertion_sort(int a[]){
  for(int i=1; i<ARRAY_SIZE; i++){
    for(int j=i; j>0; j--){
      if(a[j-1]>a[j]) swap(a[j-1], a[j]);
    }
  }
}

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

  for(int i=0; i<ARRAY_SIZE; i++){
    cout << a[i] << ' ';
  }
  cout << '\n';
  insertion_sort(a);
  for(int i=0; i<ARRAY_SIZE; i++){
    cout << a[i] << ' ';
  }
  return 0;
}

정리

앞에 있는 모든 원소가 정렬되어 있다고 가정하고 현재 가리키는 원소(a[i])를 알맞은 위치에 삽입하는 알고리즘

 

시간복잡도

최선의 경우 - 이미 정렬되어 있는 경우

insertion_sort2 코드에서 가능

n-1번 비교연산 → O(n)

 

최악의 경우 - 역으로 정렬되어 있는 경우

n-1, n-2, ... 2, 1번 비교연산

→ n*(n-2)/2 비교연산

→ O(n^2)

 

평균의 경우

O(n^2)

 

특징

stable sort

대부분 정렬되어 있는 배열일 경우 효율적

 

참조

https://www.daleseo.com/sort-insertion/