[자료구조와 함께 배우는 알고리즘][정렬 알고리즘] - 셸 정렬

shell sort는 단순 삽입 정렬의 장점은 살리고 단점을 보완해서 더 빠르게 정렬하는 알고리즘이다.

 

단순 삽입 정렬

6

4

1

7

3

9

8

# 두 번째 원소인 4부터 주목해서 바로 앞의 원소보다 큰지 작은지를 비교해서 바꿔주는 작업

 

 

4

6

1

7

3

9

8

# 세 번째 원소인 1을 주목해서 앞의 원소인 6보다 앞의 앞의 원소인 4보다도 앞으로 가야 하기에 맨 앞으로 옮겨준다.

 

 

1

4

6

7

3

9

8

# 네 번째 원소 7의 경우엔 앞의 원소 어느 것과 비교해도 다 크기 때문에 그대로 유지한다.

 

 

1

4

6

7

3

9

8

 

 

 

1

3

4

6

7

9

8

 

 

 

1

3

4

6

7

9

8

 

 

 

1

3

4

6

7

8

9

# 최종적으로 단순 삽입 정렬을 끝낸 모양

 

단순 삽입 정렬의 장 · 단점

장점 : 정렬을 이미 마쳤거나 정렬이 거의 끝나가는 경우는 속도가 아주 빠르다. 

단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.

 

---

셸 정렬

1. 원소를 그룹으로 나누어 각 그룹별로 정렬을 수행한다
2. 정렬된 그룹을 합치는 작업을 반복한다. (원소의 이동 횟수를 줄이는 방법이다.)

 

<4-정렬>

8

1

4

2

7

6

3

5

 

 

8

1

4

2

7

6

3

5

7

1

4

2

8

6

3

5

# 4칸 떨어진 원소 2개를 정렬해준다(4-정렬)

 

 

7

1

4

2

8

6

3

5

7

1

4

2

8

6

3

5

 

 

7

1

4

2

8

6

3

5

7

1

3

2

8

6

4

5

 

 

7

1

4

2

8

6

3

5

7

1

4

2

8

6

3

5

 

 

---

< 2 - 정렬 >

7

1

4

2

8

6

3

5

 

 

7

1

4

2

8

6

3

5

3

1

4

2

7

6

8

5

# 2칸 떨어진 원소를 모두 꺼내 두 그룹으로 나눠 2-정렬을 수행한다.

 

3

1

4

2

7

6

8

5

3

1

4

2

7

5

8

6

 

 

3

1

4

2

7

5

8

6

---

< 1- 정렬 >

3

1

4

2

7

5

8

6

 

1

2

3

4

5

6

7

8

---

<쉘 정렬 함수 구현 코드>

from typing import MutableSequence

def shell_sort(array):
    n = len(array)
    h = n//2 # 4-정렬/ 2-정렬/ 1-정렬 수행할 것

    whlie h > 0:
        for i in range(h,n):
            j = i - h
            tmp = array[i]
            while j >= 0 and array[j] > tmp: #4-정렬인 경운 array[0] > tmp(=array[4]])
                array[j+h] = array[j]
                j -= h
            array[j+h] = tmp

            h//=2

 

<셸 정렬 알고리즘 코드 (h*3+1의 수열 사용)>

# 셸 정렬 알고리즘 구현하기 (h*3+1의 수열 사용)

from typing import MutableSequence

def shell_sort(array):
    n = len(array)
    h = 1

    while h < n //9:
        h = h * 3 + 1
        

    whlie h > 0:
        for i in range(h,n):
            j = i - h
            tmp = array[i]
            while j >= 0 and array[j] > tmp: #4-정렬인 경운 array[0] > tmp(=array[4]])
                array[j+h] = array[j]
                j -= h
            array[j+h] = tmp

            h//=3

# 위의 코드가 제대로 섞이지 않는 문제가 있기 때문에 h*3+1 수열을 사용한 것