삽입 정렬 (Insertion Sort)

Insertion Sort는 단순한 정렬 알고리즘 중 하나이다.

 

한번의 한 원소씩 이미 정렬된 다른 원소들과 비교하여 올바른 위치에 삽입하는 정렬이다.

 

삽입 정렬은 이미 정렬되어 있을때 O(N) 의 효율이다.(Best Case)

 

Average, Worse Case의 경우 O(N^2) 이다.

 

Bubble Sort에서 발전된 형태이다.(비교 횟수를 줄였다)

 

소량의 데이터를 처리할때 좋다.

 

Stable 하다

 

무작위로 정렬된 많은 데이터의 효율이 매우 안좋다.

 

 

 

#include <iostream>

using namespace std;

void insertion_sort(int data[], int size);

int main() {
    int data[] = {3,7,9,4,5,1,3,4,6,9};
    insertion_sort(data,10);
    for (int i = 0; i < 10; i++) cout << data[i] << " ";
    return 0;
}

void insertion_sort(int data[], int size) {
    for (int i = 1; i < size; i++) {
        int temp = data[i];
        int j = i - 1;
        while (j >= 0 && data[j] > temp) {
            data[j+1] = data[j];
            j--;
        }
        data[j+1] = temp;
    }
}