[Algorithm] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

• 배열에서 특정 key 값이 정해지고, 그 key 값 앞에 있는 배열의 요소들이 오름차순으로 정렬되어 있을 때, key 값이 삽입될 위치를 찾아서 그 위치에 key 값을 삽입하면서 정렬해 나가는 방식
• 두 번째 요소를 key 값으로 정해서 두 번째 요소가 삽입될 위치를 찾아서 첫 번째 요소부터 두 번째 요소까지 정렬시키고, 다시 세 번째 요소를 key 값으로 정해서 세 번째 요소가 삽입될 위치를 찾아서 첫 번째 요소부터 세 번째 요소까지 정렬시키고 다시 네 번째 요소를 key 값으로 정해서 네 번째 요소가 삽입될 위치를 찾아서 첫 번째 요소부터 네 번째 요소까지 정렬시키고, 다섯 번째 요소를 key 값으로 정해서 다섯 번째 요소가 삽입될 위치를 찾아서 첫 번째 요소부터 다섯 번째 요소까지 정렬시키고, ... n 번째 요소를 key 값으로 정해서 n 번째 요소가 삽입딜 위치를 찾아서 첫 번째 요소부터 n 번째 요소까지 정렬시키는 방식이다.

삽입 정렬의 예

 

구현

#include <iostream>
using namespace std;

#define N 5

int main() {
    int a[N] = { 7, 6, 9, 5, 8 };
    int key, j;
    
    for (int i = 1; i < N; i++) {
        key = a[i];
        for (j = i - 1; j >= 0 && a[j] > key; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = key;
    }
    
    for (int i = 0; i < N; i++) {
        cout << a[i] << " ";
    }
        
    return 0;
}

5 6 7 8 9