#5-2-1 The Art of Computer Programming - 정렬과 검색

첫 번째 상세히 소개할 정렬은 삽입을 이용한 정렬이다.

워낙 정렬은 이전에도 많이 알고 있던 내용이었는데.. 생각보다 분량이 꽤 많아서

대체 무슨 내용이 나오려나 궁금했다.

 

"브리지 플레이어" 방법에 기초한 삽입 정렬로

레코드 R_j를 조사하기 전에 그 이전의 레코드 들이 이미 정렬되어 있다고 가정하고

정렬된 레코드들 중 적절한 위치에 R_j를 삽입한다.

 

직접 삽입 : 끼워 넣을 레코드들을 찾고 끼워 넣는 방법. sifting 또는 sinking 기법이라고도 함

이진 삽입 및 양방향 삽입 : 그다지 효율적이지 않음

셸 삽입 : 레코드들을 두 개씩 여덟 그룹으로, 그리고 4그룹, 2그룹, 1그룹으로 줄여나가면서 정렬

목록 정렬 : 단방향 연결로만 구성해서 목록을 증가 순서로 구성

주소 계산 정렬 : 직접 삽입이라는 단순한 방법을 개선하는 방법. N에 비례하는 추가적인 저장공간 요구.

 

생각보다 다양한 삽입 정렬이 있다는 걸 알게 되었다.

셸 삽입 개념이 어려움 ㅠㅠ