셸 정렬 (shell sort) 알고리즘

셸 정렬의 등장

삽입 정렬의 보완

삽입 정렬은 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.

역순으로 정렬된 최악의 경우, 이동을 많이 해야 최종 위치에 다다를 수 있다.

 

 

삽입 정렬의 시간복잡도

O(n) : 이미 정렬된 최선의 경우, n-1번의 1회차 비교만 수행한다.

O(n^2) : 역순으로 정렬된 최악의 경우 1+2+3+ ... + (n-2) + (n-1) = 총 n(n-1)/2번 이동한다.

 

 

 

 

셸 정렬

1. 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.
2. 데이터를 다시 잘게 나누어서 삽입 정렬한다.
3. 이렇게 계속 하여 마침내 정렬이 된다.

 

나누는 간격 k

• 간격 k의 초깃값 : (데이터 개수) / 2
• 매 회전마다 k는 절반으로 나눈다. 단, 항상 홀수가 되도록 값을 수정한다. (짝수인 경우 +1)
  • 홀수로 다루는 것이 성능에 더 좋은 영향을 끼친다는 연구 결과..
• k가 1이될 때까지 반복한다.

 

 

 

 

 

 

리스트를 부분 리스트로 나눈 후 삽입정렬을 할 때, 각 데이터는 긴 거리를 이동한다.

따라서 각 요소가 최종 위치에 있을 확률이 높아진다.

(삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다. )

 

 

셸 정렬에서 간격이 1일 때 삽입 정렬을 하지만, 배열의 처음 상태보다 어느 정도 정렬이 되어있으므로, 처음부터 삽입 정렬을 하는 것보다 속도가 빠르다.

 

 

 

 

시간복잡도

최선: T(n) = O(n) : 삽입 정렬처럼 이미 정렬된 경우, 1회차에서 비교만 수행한다.

평균: T(n) = O(n^1.3) ~ O(n^1.5) : 계산방법이 힘들다고 하니 알아두기만 하자.
최악: T(n) = O(n^2) 

 

 

불안정 정렬

셸 정렬은 정렬 이후 초기 순서와 달라질 수 있는 불안정 정렬이다.

[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

 

 

 

 

 

 

출처

https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog