콘텐츠로 건너뛰기
Home » diminishing incremental sort

diminishing incremental sort

셸 정렬 (Shell Sort)

셸 정렬은 정렬 방법의 원리로만 보자면 “분할 증분 정렬”(diminishing incremental sort)이라고도 불리는 방법이며, 굉장히 오래된 정렬 알고리듬 중 하나이다. 이 정렬 방법은 삽입 정렬을 근간으로 하면서 삽입 정렬의 성능을 간단한 아이디어로부터 크게 증가시키는 방법이다.

삽입 정렬은 왼쪽에 있는 원소부터, 그 원소가 이동할 수 있는 ‘가장 왼쪽 자리’에 그 값을 삽입하여 정렬해 나가는 방식이다. 이 때 ‘삽입’을 위한 공간을 만들기 위해 원래자리부터 삽입될 자리 사이의 값들이 하나씩 오른쪽으로 이동해야 한다. 따라서 삽입 정렬은 어떤 원소가 이동해야 할 거리가 크면 클수록 효율이 떨어지며 배열이 반대로 정렬되어 있는 경우가 이에 해당할 것이다.

더 보기 »셸 정렬 (Shell Sort)