관리 메뉴

Kim-Baek 개발자 이야기

삽입 정렬 (Insertion Sort) 본문

컴퓨터 공학/자료구조, 알고리즘

삽입 정렬 (Insertion Sort)

킴백 개발자 2020. 9. 26. 10:00

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;
    }
}
반응형

'컴퓨터 공학 > 자료구조, 알고리즘' 카테고리의 다른 글

퀵 정렬 (Quick Sort)  (0) 2020.09.28
병합 정렬 (Merge Sort)  (0) 2020.09.27
선택 정렬 (Selection Sort)  (0) 2020.09.25
BFS (Breath First Search)  (0) 2020.09.23
[Tree] 트리 순회 - Tree traversal  (0) 2020.08.07
0 Comments
댓글쓰기 폼