Sort/정렬 - Insertion Sort/삽입 정렬

삽입 정렬은 선택한 요소를 "그보다 더 앞쪽의 알맞은 위치에 삽입"하는 작업을 반복해 정렬하는 알고리즘이다.

선택 정렬과 비슷해 보이지만 선택 정렬은 "값이 가장 작은 요소를 선택해서 옮기는 것"이다. 

바로 알고리즘을 설명하자면, 요소를 선택하고 그 요소의 값보다 작은 요소를 만날 때까지 이웃한 왼쪽의 요소를 대입하는 작업을 반복하다 멈추면 멈춘 위치에 그 요소를 대입한다.

 

알고리즘

1. 정렬된 열의 왼쪽 끝에 도달함.

2. tmp보다 작거나 같은 key값을 갖는 항목을 발견함.

이 두 조건을 만족할 때까지 설명한 작업을 반복한다.

 

코드

void insertion(int arr[], int size){
    int i, j;
    for(i = 1; i < size ; i++){ // i까지는 정렬이 끝남
        int tmp = arr[i]; // tmp는 선택한 요소
        for(j = i; j > 0 && arr[j - 1] > tmp; j--){ // 조건이 맞을 때 까지 반복
            arr[j] = arr[j - 1]; // 값을 대입해줌
        }
        arr[j] = tmp; // 알맞은 위치를 찾으면 tmp를 대입
    }
}

j가 0보다 크고 arr[j - 1]의 값이 클 때 작업을 반복한다는 것을 알 수 있다.

하지만 삽입정렬도 버블, 선택 정렬과 마찬가지로 O(n^2)의 시간 복잡도를 가져서 효율적인 정렬방법이라고는 할 수 없다.

 

이거에서 조금더 나아가 배열의 요소를 그룹으로 나눠 그룹별로 삽입 정렬을 수행하고 그 그룹을 합치면서 정렬을 반복해 요소의 이동 횟수를 줄일 수 있는 Shell Sort가 있다. 시간 복잡도는 O(n^1.25)로 기존의 삽입 정렬의 속도에 비해 매우 빠르다 하지만 어차피 이 정렬 알고리즘 보다 더 빠른 정렬 알고리즘이 있기에 마찬가지로 잘 사용하지 않으니

자세한 설명은 하지않고 코드만 작성하도록 한다.

 

코드

void Shell_Sort(int arr[], int size){
    int i,j,h;
    for(h = size / 2; h > 0; h /= 2){
        for(i = h; i < size; i++){
            int tmp = arr[i];
            for(j = i - h; j >= 0 && arr[j] > tmp; j -= h){
                arr[j + h] = arr[j];
            }
            arr[j + h] = tmp;
        }
    }
}

 

전체 코드

#include <iostream>
using namespace std;

void Insertion_Sort(int arr[], int size){
    int i, j;
    for(i = 1; i < size ; i++){
        int tmp = arr[i];
        for(j = i; j > 0 && arr[j - 1] > tmp; j--){
            arr[j] = arr[j - 1];
        }
        arr[j] = tmp;
    }
}

void Shell_Sort(int arr[], int size){
    int i,j,h;
    for(h = size / 2; h > 0; h /= 2){
        for(i = h; i < size; i++){
            int tmp = arr[i];
            for(j = i - h; j >= 0 && arr[j] > tmp; j -= h){
                arr[j + h] = arr[j];
            }
            arr[j + h] = tmp;
        }
    }
}



int main(){
    int arr[] = {32,12,54,99,76,87,23,98,16,50}; // size = 10
    cout << "Before sorting : ";
    for(auto i : arr){
        cout << i << ' ';
    }
    cout << '\n';
    Shell_Sort(arr,10);
    cout << "After  sorting : ";
    for(auto i : arr){
        cout << i << ' ';
    }
    return 0;
}