[알고리즘] 셸 정렬(shell sort)

셸 정렬

단순 삽입 정렬(straight insertion sort) 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘

단순 삽입 정렬의 장점과 단점

• 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나는 상태에서는 속도가 아주 빠르다.
• 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.

사용방법 (정렬 시에는 모두 단순 삽입 정렬을 이용)

ex) 8개 배열 일 때

4-정렬 : 서로 4칸씩 떨어진 원소를 4개 그룹으로 나누어정렬하는 방법

2-정렬 : 2칸씩 떨어진 원소를 모두 꺼내 두 그룹으로 나누고 정렬 실행

1-정렬 : 정렬 되어 나온것들(3,1,4,2,7,5,8,6) 단순 삽입 정렬로 정렬

총 7번의 정렬 실행

• 2개 원소에서 4-정렬 수행 (4그룹, 4번)
• 4개 원소에서 2-정렬 수행 (2그룹, 2번)
• 8개 원소에서 1-정렬 수행 (1그룹, 1번)

셸 정렬 알고리즘 구현하기

a=[8,1,4,2,7,6,3,5]
n=len(a)
h=n//2

while h>0:
    for i in range(h,n):
        j = i-h
        tmp = a[i]
        while j >=0 and a[j] > tmp:
            a[j+h] = a[j]
            j-=h
        a[j+h]=tmp
    h//= 2

문제 발생

그림 파란색 그룹 (8,7),(4,3) 그리고 검은색 그룹 (1,6),(2,5)은 섞이지 않는다. 그룹으로 나누어 정렬했지만 충분히 그 기능을 하지 못한다.

=> 해결방법

• h값이 서로 배수가 되지 않도록 해야 한다.
• ex) h= ...->121->40->13->4->1
• 3배한 값에 1을 더하는 방식
  • 이것도 h의 초기값이 지나치게 크면 효과가 없다.
  • 따라서 배열의 원소 수인 n을 9로 나누었을 때 그 몫을 넘지 않도록 정한다.

    코드

    a=[8,1,4,2,7,6,3,5]
    n=len(a)
    h=1
    while h<n//9:
    h=h*3+1
    while h>0:
    for i in range(h,n):
      j = i-h
      tmp = a[i]
      while j >=0 and a[j] > tmp:
          a[j+h] = a[j]
          j-=h
      a[j+h]=tmp
    h//= 2
    print(a)