셸 정렬이란?

1. 셸 정렬
   1-1. 셸 정렬이란?
   1-2. 예시
   1-3. 소스코드
   1-4. 셸 정렬의 시간 복잡도
   1-5. 셸 정렬은 삽입 정렬보다 얼마나 빠를까?

 

 

 

---

 

1. 셸 정렬

1-1. 셸 정렬이란?

셸 정렬은 삽입 정렬의 개선판 정도로 생각할 수 있다.

삽입 정렬은 거의 정렬되어 있는 수열이 주어졌을 때 좋은 효율을 보여준다는 장점이 있었지만

그 반대로 역순에 가까운 수열이 주어지면 그만큼 좋지 못한 효율을 보여주었다.

 

그래서 옛날에 도널스 셸이라는 사람이

"흠.. 수열을 어느 정도 정렬되게 바꾼 다음 삽입 정렬을 쓰면 좋지 않을까?" 해서 나온 게 셸 정렬이다.

실제로도 셸 정렬을 할 때 삽입 정렬을 사용한다. 그러니 삽입 정렬을 아직 모른다면 먼저 배우고 오자.

 

1-2. 예시

위와 같이 내림차순에 가까운 수열이 있다고 하자.

지금부터 숫자들을 그룹으로 나눌 건데 한 그룹에 몇 개를 넣을지 정해주어야 한다.

몇 개를 넣을지 정하는 규칙은 다음과 같다.

 

1. 맨 처음에는 한 그룹에 들어가는 숫자의 개수(= 이후로는 gap이라 칭한다)를 수열의 개수 / 2로 정해준다.
2. gap은 매 회전마다 절반으로 줄어든다.
3. 만약 gap이 짝수인 경우 +1을 해서 홀수로 만든다.

 

즉, 지금 숫자가 10개 있으니 10 / 2 = 5

5개씩 묶으면 된다.

 

 

 

• 첫 번째 바퀴

gap이 5니까 숫자를 5개씩 묶어 위와 같이 놓아보자.

 

이제 해야 할 것은 세로로 숫자를 읽었을 때 오름차순이 되도록 하는 것이다.

10이 3보다 크니까 둘의 자리를 바꾸자. (삽입 정렬 이용)

 

바로 이렇게 말이다!

 

 

그런 방식으로 모든 숫자들을 비교하며 자리를 바꿔나간다.

마지막으로 위와 같이 1, 9의 자리까지 정렬해주면 끝!

숫자들을 다시 일렬로 나열해보면 3, 4, 2, 5, 1, 10, 7, 8, 6, 9이다.

수열들이 거의 내림차순이었던 아까보다는 조금 나아진 모습이다.

 

 

 

• 두 번째 바퀴

 

첫 번째 바퀴의 gap이 5였으니 이번에는 (5 / 2) + 1 = 3이 된다.

3개씩 묶고 나서도 똑같이 세로로 숫자들을 보고 정렬해주면 된다. (삽입 정렬 이용)

위와 같이 3, 5, 7, 9의 경우는 정렬할 게 없기 때문에 옆으로 넘어가면 된다.

 

세 줄 모두 정렬을 마치면 위와 같은 모습이 된다.

 

 

 

• 세 번째 바퀴

앞서 두 번의 정렬을 했더니 숫자들이 거의 오름차순으로 정렬된 것을 확인할 수 있다.

완전히 정렬되진 않았지만 각 숫자들이 자기가 위치해야 할 곳 근처에 있다.

 

마지막으로 gap은 3 / 2 = 1이 되며 이 상태로 삽입 정렬을 하면 정렬은 끝이 난다.

 

 

 

1-3. 소스코드

 

소스코드를 짜기 전에 알아두어야 할 것이 있다.

[목차 1-2]에서는 빠른 이해를 위해 위와 같은 상황에서 세로 그룹을 삽입 정렬하라고만 하고 넘어갔는데

막상 코드를 짜 보면 코드가 굉장히 지저분해진다는 걸 알 수 있다.

 

위와 같이

0,3 / 0,3,6 / 0,3,6,9 번째 인덱스의 삽입 정렬을 수행하고

1,4 / 1,4,7 번째 인덱스의 삽입 정렬을 수행하고...

이 순서로 하려면 for문이 복잡해지니 다음과 같이 삽입 정렬을 수행하면 편하다.

 

0,3 번째 인덱스의 삽입 정렬을 수행하고

1,4 번째 인덱스의 삽입 정렬을 수행하고

2,5 번째 인덱스의 삽입 정렬을 수행하고

 

0,3,6 번째 인덱스의 삽입 정렬을 수행하고

1,4,7 번째 인덱스의 삽입 정렬을 수행하고

.

.

.

이런 순으로 실행하면 for문이 좀 더 간결해진다.

 

public static void shellSort(int[] arr) {
    int len = arr.length;
		
    // gap의 크기를 정해준다. 
    for(int gap=len/2; gap>0; gap/=2) {
			
        // gap이 짝수면 1을 더해 홀수로 만들어준다.
        if(gap%2 == 0) gap++;
			
        // 삽입 정렬
        for(int i=gap; i<len; i++) {
            int temp = arr[i];
            int j = i-gap;
				
            while(j >= 0 && arr[j] > temp) {
                arr[j+gap] = arr[j];
                j-=gap;
            }
            arr[j+gap] = temp;
        }
    }
}

소스 코드는 위와 같이 작성하면 된다.

 

 

1-4. 셸 정렬의 시간 복잡도

셸 정렬이 삽입 정렬보다 빠른 이유는 위처럼 여러 번에 거쳐 이동해야 하는 거리를

 

 

한 번에 이동할 수 있기 때문이다. 한 번에 큰 거리를 이동함으로써 불 필요한 동작을 최소화하는 것이다.

 

 

이때 gap은 셸 정렬의 시간 복잡도와 굉장히 밀접한 관계를 가진다.

gap을 몇으로 설정하느냐에 따라 셸 정렬의 시간 복잡도가 달라지게 된다.

gap값은 무조건 작다고 좋은 것도 아니오 크다고 좋은 것도 아니다.

그렇다고 모든 상황에 best인 gap을 구하는 규칙이 있는 것도 아니다.

 

 

 

[목차 1-2]에서 gap을 정하는 규칙에 대해 소개했지만 사실 이건 셸 정렬을 사용하기 위한 절대적인 규칙은 아니다.

사람들은 최적의 gap 값을 구하기 위한 규칙을 연구했고 그 규칙 중 하나가 [목차 1-2]에서 소개한 규칙인 것이다.

 

모든 상황에서 best인 규칙은 없는 것 같다. 상황별로 추천하는 gap 규칙은 여기에서 확인할 수 있다.

 

 

1-5. 셸 정렬은 삽입 정렬보다 얼마나 빠를까?

 

랜덤한 숫자 10만개를 정렬해보았다.

 

느려 터진 버블, 선택, 삽입 정렬에 비해 셸 정렬이 굉장히 빠르다는 걸 알 수 있었다.

 

 

 

---

💡 느낀 점

• 셸 정렬은 빠르긴 하지만 gap값 때문에 편차가 생겨서 잘 안 쓰이게 되지 않을까 싶다.
• 빠르긴 빠른데 더 빠른 정렬도 있어서.. 이런 게 있다 정도만 알아두면 좋을 것 같다.

📘 참고한 자료

• 셸 정렬 - st-lab님 블로그
• Shellsort - 위키피디아

---