Shell 정렬 (셸 정렬)

Shell 정렬

Shell 정렬은 “분할 증분 정렬”(diminishing Incremental Sort)이라고도 불리는 방법으로 삽입정렬을 원래 리스트를 더 작은 서브리스트들로 나눠서 정렬함으로써 성능을 향상시키는 방법이다. 즉 리스트를 더 작은 조각들로 나눈다음 각각을 삽입정렬을 사용하여 정렬한다. 이 때 서브리스트들을 나누는 기준을 정하는 방법이 독특한데, 연속된 원소들로 구성된 서브리스트를 나누는게 아니라 i개씩 건너뛰고 원소들을 선택하여 서브리스트를 만든다. 이 때 i는 gap이라고도 불리운다. Shell 정렬 (셸 정렬) 더보기