[Algorithm] 삽입 정렬 (Insert Sort)

개념

첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법

 

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)

[Algorithm] 순차 탐색 (Sequential Search)

 

[용어/개념] AAA(Authentication Authorization Accounting) 프로토콜

[용어/개념] AAA(Authentication Authorization Accounting) 프로토콜