반응형
안녕하세요. BlockDMask 입니다.
오늘은 간단한 정렬 알고리즘 중에 삽입 정렬 (Insertion Sort) 에 대해서 알아보겠습니다.
이상한 곳이 있으면, 댓글로 말해주시기 바라겠습니다.
댓글을 보고 고치도록하겠습니다.
따끔한 지적 부탁드리겠습니다.
0. 원리
Insertion Sort 는 말 그대로 '삽입' 꽂아 넣는 정렬입니다.
자신보다 앞의 원소가 큰지 작은지 비교를 하여서 자신의 위치를 찾아서 '삽입' 하는 정렬입니다.
앞의 원소를 비교해야 하기 때문에 arr[1]~arr[n] 까지 진행합니다. (두번째 원소인 arr[1] 부터 시작.)
삽입을 하면 데이터가 하나씩 밀려야 하기 때문에 배열이 길어질수록 효율이 떨어집니다.
그림을 통해서 과정을 살펴 보겠습니다. (오름차순을 기본으로 하겠습니다)
1. 코드 및 결과
T) C/C++ 로 구현한 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<stdio.h> #define MAX_LEN 5 void InsertionSort(int * arr){ int i, j; int key; for(i=1; i< MAX_LEN; i++){ key = arr[i]; for(j=i-1; j>=0; j--){ if(arr[j] > key){ //key의 앞자리를 하나씩 보면서 비교 arr[j+1] = arr[j]; //앞자리 값이 key값보다 크다면 하나씩 이동 }else{ //key보다 작은 값이 나오면 break; break; } } arr[j+1] = key; //그 자리에 key값을 넣는다. } } int main(void){ int arr[MAX_LEN] = {9, 5, 3, 7, 1}; int i; for(i=0; i<MAX_LEN; i++){ printf("%d ", arr[i]); } printf("\n"); InsertionSort(arr); for(i=0; i<MAX_LEN; i++){ printf("%d ", arr[i]); } return 0; } | cs |
> 결과
2. 시간 복잡도
이중 for문 내부의 조건문 if가 n * n-1 번 일어나므로 시간복잡도 빅오는 입니다.
다음시간에는 선택 정렬 (Selection Sort)에 대해서 포스팅 하겠습니다.
반응형
'<개인공부> > [Algorithm]' 카테고리의 다른 글
퀵 정렬 (Quick Sort) 이론과 코드 (3) | 2017.10.19 |
---|---|
[탐색] lower_bound, upper_bound (5) | 2017.10.11 |
[탐색] 이진탐색 (Binary Search) 구현 방법 (4) | 2017.10.09 |
[알고리즘의 정의] Algorithm? (0) | 2017.10.07 |
선택 정렬 (Selection Sort) 이론과 코드 (3) | 2017.09.24 |
버블정렬 (Bubble Sort) 이론과 코드 (2) | 2017.07.31 |
[유클리드 알고리즘] GCD 최대공약수 (반복문, 재귀) (4) | 2017.07.14 |