11. 쉘 정렬

https://tinyurl.com/y4glkjh4

---

쉘정렬

삽입 정렬이 거의 정렬된 배열에서 최적의 성능을 내는 것에서 착안한 정렬 방법이다.

삽입 정렬을 띄엄띄엄한 간격으로 먼저 수행하고, 그 간격을 점차 좁혀나가면서 최종적으로는 거의 정렬된 배열을

삽입 정렬로 마무리하게 된다.

지저분해 보이지만 삽입 정렬의 특성을 잘 이용한 정렬로, 실제 성능은 힙 정렬 등에 버금갈 정도로 빠르다.

이 정렬 알고리즘의 핵심은 어떤 간격으로 정렬을 수행해 나갈 것이냐는 것인데, 간격에 따라 시간 복잡도도 제각각이다.

간격을 잘 선택하는 경우 까지도 가능하다고 하는데 일반적인 데이터 크기에 모두 적용할 수 있는 것은 아니다. 알고리즘 자체가 시간 복잡도가 명확하지 않고 퀵 정렬이나 병합 정렬에 비해 크게 나을 것이 없기에 일반적으로 쓰는 알고리즘은 아니다.

셸 정렬이란 이름은 개발자인 도널드 셸의 이름을 딴 것으로 유닉스의 셸과는 관련이 없다.

이것을 잘 몰랐는지 예전 번역서에는 '껍질 정렬'로 오역된 책이 있었다.

지금도 껍질 혹은 틀을 의미한다면서 큰 틀을 잡아나가면서 정렬해나가기에 셸 정렬이라는 말이 있는데 틀린 말이다.

https://youtu.be/kPRA0W1kECg?t=216

뾰오오오옥 (3분38초 쉘 정렬 부분부터 재생)

https://youtu.be/CmPA7zE8mx0

역시나 춤추는 알고리즘 설명 영상

---

쉘 정렬 구체적 플로우

정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 

이때, k를 ‘간격(gap)’ 이라고 한다.

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

간격의 초깃값: (정렬할 값의 수)/2

생성된 부분 리스트의 개수는 gap과 같다.
각 싸이클마다 간격 k를 절반으로 줄인다. 

즉, 각 싸이클이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
간격은 홀수로 하는 것이 좋다.
간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수로 만든다.
간격 k가 1이 될 때까지 반복한다.

---

쉘 정렬의 예제

10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

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

1 싸이클

처음 간격을 (정렬할 값의 수:10)/2 = 5로 하고, 다섯 번째 요소를 추출해서 부분 리스트를 만든다. 

만들어진 5개의 부분 리스트를 삽입 정렬로 정렬한다.

2  싸이클

다음 간격은 = (5/2:짝수)+1 = 3으로, 1싸이클에서 정렬한 리스트 중 세 번째 요소를 추출해서 부분 리스트를 만든다. 

만들어진 3개의 부분 리스트를 삽입 정렬로 정렬한다.

 

3 싸이클

다음 간격은 = (3/2) = 1으로 하고, 간격 k가 1이므로 마지막으로 정렬을 수행한다.

만들어진 1개의 부분 리스트를 삽입 정렬로 정렬한다.

예제 C 코드

# include <stdio.h>
# define MAX_SIZE 10

// gap만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last까지
void inc_insertion_sort(int list[], int first, int last, int gap){
  int i, j, key;

  for(i=first+gap; i<=last; i=i+gap){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-gap까지이므로 i-gap번째부터 역순으로 조사한다.
    // j 값은 first 이상이어야 하고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+gap번째로 이동
    for(j=i-gap; j>=first && list[j]>key; j=j-gap){
      list[j+gap] = list[j]; // 레코드를 gap만큼 오른쪽으로 이동
    }

    list[j+gap] = key;
  }
}

// 셸 정렬
void shell_sort(int list[], int n){
  int i, gap;

  for(gap=n/2; gap>0; gap=gap/2){
    if((gap%2) == 0)(
      gap++; // gap을 홀수로 만든다.
    )

    // 부분 리스트의 개수는 gap과 같다.
    for(i=0; i<gap; i++){
      // 부분 리스트에 대한 삽입 정렬 수행
      inc_insertion_sort(list, i, n-1, gap);
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16};

  // 셸 정렬 수행
  shell_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}
//https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html

---

Shell 정렬 파이썬 코드

코드.

def gapInsertionSort(alist, interval, startposition):
    # the 'nth' element in sublist is alist[startposition + gap*n]
    for index in range(startposition, len(alist), interval):
        position = index
        currentValue = alist[index]
        while position >= interval and alist[position-interval] > currentValue:
            alist[position] = alist[position - interval]
            position -= interval
        alist[position] = currentValue

def shellSort(alist):
    interval = len(alist) // 2
    while interval > 0:
        for i in range(interval):
            gapInsertionSort(alist, interval, i)
            print(alist)
        interval = interval // 2

alist = [8,6,5,3,2,4,7,1]
shellSort(alist)
print(alist)

결과

갭 insertion sort + shell sort

---

쉘 정렬의 시간복잡도

평균:
최악의 경우:

출처: https://tinyurl.com/y287lhew