반응형
개념
첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법
I. 삽입 정렬 (Insert Sort)의 개요
가. 삽입 정렬의 정의
- 첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법
나. 삽입 정렬의 특징
- 간단하지만 레코드의 이동이 많은 알고리즘
- 비교적 크기가 작은 데이터 집합 정렬에 유리함.
- 수행시간 복잡도: O(n2)
Ⅱ. 삽입 정렬의 단계 및 사례
가. 삽입 정렬의 단계
- 삽입 대상 위치를 2번째부터 마지막까지 지정 - 비교 대상을 처음부터 바로 전까지 지정 - 정렬 대상의 값들과 뽑아낸 요소와 비교 - 삽입할 값보다 큰 값을 가진 모든 요소들을 한 자리씩 오른쪽으로 이동 - 새로 생긴 빈 자리에 해당 요소를 삽입 - 전체 데이터 집합의 정렬이 완료될 때까지 반복 |
반응형
나. 삽입 정렬의 사례
void insertion_sort(element list[], int n) { int i, j; element next; for(i = 1; i < n; i++){ next = list[i]; for(j = i - 1; j >= 0 && next.key < list[j].key; j--){ list[j + 1] = list[j]; }; list[j + 1] = next; } } |
[Algorithm] 순차 탐색 (Sequential Search)
[용어/개념] AAA(Authentication Authorization Accounting) 프로토콜
반응형