삽입정렬 (feat. Insert Sort)

 

 

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

삽입정렬은 현재의 인덱스값이 어느 인덱스에 삽입되어야 할지를 비교하며 이루어집니다.

선택정렬의 경우, 하나의 값을 기준으로 그보다 더 작은 (더 가장 작은) 인덱스를 찾고 두 인덱스의 값을 서로 swap 하는 방식입니다.

하지만 삽입정렬의 경우, 하나의 값을 기준으로 그보다 더 큰값이 존재한다면 큰값이 있는 인덱스를 뒤로 한칸씩 밀어나간다는 개념입니다.

즉, 선택정렬은 swap의 개념이지만 삽입정렬은 insert에 개념으로 접근됩니다. (배열은 insert라는 개념이 없으므로 한 칸씩 뒤로 미는 형태로 구현됩니다.)

 

반응형

 

위와 같은 방법으로 삽입정렬을 구현할 수 있습니다.

모든 배열의 값들을 비교하므로 브루트포스 알고리즘 기법이라고 할 수 있습니다.

 

삽입정렬을 코드로 구현하면 아래와 같습니다.

 

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <random>
#include <algorithm>
using namespace std;
void insert_sort(int* arr, int length){
    for(register int i = 1, j; i < length; ++i){
        register int value = arr[i];
        for(j = i - 1; j >= 0; --j)
            if(arr[j] > value)
                arr[j + 1] = arr[j];
            else
                break;
        arr[j + 1] = value;
    }
}
int main(){
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<int> range(0, 10000);
    int arr[20];
    for(auto& v : arr)
        v = range(mt);
    cout << "before : ";
    for(auto& v : arr)
        cout << v << " ";
    cout << "\n";
    insert_sort(arr, sizeof(arr) / sizeof(arr[0]));
    cout << "after : ";
    for(auto& v : arr)
        cout << v << " ";
    return 0;
}
// *&)*@*

 

삽입정렬 (위키백과)