셸 (Shell Sort) 정렬 란?

셸 정렬이란 ?

삽입 정렬보다 개선된 정렬이라고 생각할 수 있다.

삽입 정렬은 거의 정렬되어 있다면, 좋은 효율을 보여준다는 장점이 있었지만? 그 반대로 역순에 가까운 수열이 주어진다면 그만큼 좋지 않은 효율을 보여주었다.

그래서

"수열을 어느정도 정렬되게 바꾼 다음에 삽입 정렬을 쓰면 좋지 않을까?" 라는 생각으로 만들어 진 게 셸 정렬이다.

삽입과는 다르게 셸은 전체의 리스트를 한 번에 정렬하지 않는다.

먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고,

각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.

모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수(gap)의 부분 리스트로 만든 후

이 과정을 반복한다.

셸 정렬 장단점은 ?

1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동하므로 교환되는 요소들이 삽입정렬보다는

최종 위치에 더 가까이 있을 가능성이 높아진다.

2. 부분 리스트는 어느정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되었을 때, 삽입 정렬이 훨씬 빠르게 수행된다.

3. 셸 정렬은 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬에 속합니다.

Ex.

[25, 25, 6, 20, 4, 3, 22, 1, 0, 15, 16] k = 5

[3, 25, 6, 20, 4, 16, 22, 1, 0, 15, 25] k = 5

시간복잡도는 ?최선일 때는 삽입 정렬처럼 이미 정렬된 경우, 1회차에서 비교만 수행한다. O(n)평균일 때는 계산법이 힘들다.. O(n^1.5) 이다.최악일 때는 O(n²) 이다.

위에서 언급한 일정한 기준에 따라? (간격) 는 어떻게 할까?

수학자나 컴퓨터 과학자들 사이에 열띤 토론이 진행되고 있고, 다양한 방법들이 많이 나왔다.

어떠한 방법은 구현하기에 편하고 간단하지만 효율성이 떨어진고,

어떤 방법은 효율성이 좋은 대신 구현하기에 너무 복잡하고 어렵다.

이러한 저울질을 통해 현재 셸 정렬은 가장 보편적으로 쓰이는 방법은 3h+1을 사용하는 방법이다.

즉, 정렬을 진행하는 간겨을 3h+1... 123, 40, 13, 4, 1 과 같이 설정하는 방법이다.

JS Property Trading