Insertion Sort (삽입 정렬) / Shell Sort (셸 정렬)

Insertion Sort (삽입 정렬)

앞서 본 다른 정렬 알고리즘과 마찬가지로, 삽입 정렬도 '정렬된 부분'과 '정렬되지 않은 부분'으로 나뉘는데, 진행 방향은 왼쪽에서 오른쪽으로 가는 것으로 하자.

다음과 같은 배열이 있다. 인덱스는 0부터 시작한다.

20

35

-15

7

55

1

-22

먼저 0번째 요소는 정렬된 부분으로 가정한다. 하나 밖에 없으니까.

주황색은 정렬된 부분, 초록색은 정렬되지 않은 부분이다.

20

35

-15

7

55

1

-22

정렬되지 않은 부분의 맨 왼쪽 인덱스(firstUnsortedIndex; 위의 경우 1)에 위치한 요소(newElement; 위의 경우 35)를, 정렬된 부분의 맨 오른쪽 요소(i)부터 왼쪽으로 하나씩 비교한다. 비교하면서 newElement보다 큰 요소가 있으면 오른쪽으로 shift 시키고, newElement보다 작거나 같은 요소가 나타나면 멈추고 그 위치에 newElement를 삽입하면 된다. 

20은 35보다 작으므로, 이동할 것이 없다.

20

35

-15

7

55

1

-22

이제 i는 1, firstUnsortedIndex는 2이고, newElement는 -15가 된다.

-15보다 35가 크니, 35를 한 칸 오른쪽으로 shift 시킨다.

20

35

35

7

55

1

-22

-15보다 20이 크니, 20을 한 칸 오른쪽으로 shift 시킨다. 맨 처음까지 왔으니 이제 newElement인 -15를 위치시킨다. 3개 요소의 정렬이 완료되었다.

-15

20

35

7

55

1

-22

같은 방법으로, i는 2, firstUnsortedIndex는 3이고, newElement는 7이다. 나머지는 중간 과정 생략.

-15

7

20

35

55

1

-22

-15

7

20

35

55

1

-22

-15

1

7

20

35

55

-22

-22

-15

1

7

20

35

55

정렬이 완료 되었다!

---

삽입 정렬 주요 사항

• In-place algorithm (제자리 정렬)
  약간의 추가적인 공간이 필요하기는 하지만, 그 추가 공간이 정렬하고자 하는 요소의 개수와 독립적이라면, 즉 관련이 없다면 제자리 정렬이라고 볼 수 있다.
  
• 시간 복잡도: O(N^2); Quadratic
• Stable algorithm (안정적)
  만약 정렬되지 않은 부분에서 9를 고르고, 정렬된 부분을 왼쪽으로 탐색하다가 역시 9를 만났다면, 교환하지 않을 것이다. 위의 설명에서, 작거나 "같은" 요소를 만나면 탐색을 중지한다고 했다. 탐색을 멈추고 하나의 pass가 그대로 끝나므로, 두 개의 같은 수의 순서는 그대로 유지된다. 즉 안정적이다.

public class Main {
    public static void main(String[] args) {

        int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

        for (int firstUnsortedIndex = 1; firstUnsortedIndex < intArray.length;
                firstUnsortedIndex++) {
            int newElement = intArray[firstUnsortedIndex];
            int i;

            // newElement보다 큰 요소들은 오른쪽으로 shift (작거나 같은 요소가 나올 때까지 반복)
            for (i = firstUnsortedIndex; i > 0 && intArray[i - 1] > newElement; i--) {
                intArray[i] = intArray[i - 1];  // 왼쪽에서 오른쪽으로 shift
            }
            // shift가 끝나고 남은 자리에 newElement를 삽입
            intArray[i] = newElement;
        }

        for (int i = 0; i < intArray.length; i++) {
            System.out.print(intArray[i] + " ");
        }
    }
}

삽입 정렬은 조건에 따라서 shift만 하면 되기 때문에, swap이 필요 없다.

마지막으로, 첫번째 pass에서 -22의 경우 가장 작은 값이기 때문에 다른 모든 값들을 전부 shift시켜야만 한다. 이것이 삽입 정렬의 단점인데, 이를 보완할 수 있는 Shell Sort(셸 정렬)이 있다. 다음 포스트에서 정리해보겠다.

---

Shell Sort (셸 정렬)

그런데 생각해보면, 삽입정렬을 '거의 정렬된 배열'에 적용할 경우 linear time(O(n))까지도 기대해볼 수 있다. shift 횟수가 줄어들기 때문이다. 

이 점에 착안해 Donnell Shell이라는 사람이 만든 것이 바로 Shell Sort(셸 정렬)이다. 삽입 정렬을 하기 전에 어느 정도 정렬을 해놓고 시작하면 훨씬 빨라지지 않을까? 이것이 셸 정렬의 기본 아이디어다.

• 셸 정렬은 삽입 정렬의 변형이다.
• 삽입 정렬은 바로 옆의 요소부터 하나하나 검사하지만(gap value가 1), 셸 정렬은 먼 곳에 있는 요소부터 검사한다.
• 알고리즘이 실행됨에 따라 gap(두 요소 사이의 거리)이 줄어든다. gap value가 1이 될 때까지 진행하는데, 그 이후의 과정은 결국 삽입 정렬과 동일한 것이 된다. 
• 셸 정렬은 삽입 정렬 전 예비 과정을 먼저 수행함으로써, 보다 정렬된 상태를 만든 다음에 삽입정렬을 수행하고자 하는 것이다. 이렇게 하면 gap value가 1일 때, 즉 삽입 정렬 시에 필요한 shifting의 개수를 줄일 수 있게 된다. 이것이 셸 정렬의 목표다.

그렇다면, 셸 정렬을 처음 시작할 때의 gap value는 어떻게 설정해야 할까? 셸 소트 위키피디아의 "Gap sequences" 부분을 보면, gap을 계산하는 다양한 방법들을 확인할 수 있다. gap을 어떻게 계산하느냐에 따라 시간복잡도에 차이가 있는데, 물론 아무 방식이나 택해도 전혀 상관 없다. 가장 흔하게 쓰이는 방식으로는 "Knuth Sequence"라는 것이 있다. k가 (1, 2, 3, ...)일 때 (3^k - 1) / 2의 수식을 이용하여 gap value가 1, 4, 13, 40, 121, 364, ... 과 같이 나아가는 방식이다. 이 중에서 배열의 길이와 가장 가깝되 더 크지는 않은 gap value를 고르면 된다.

간단한 예시를 살펴보자.

20

35

-15

7

55

1

-22

위와 같은 배열이 있을 때, 배열이 작으니 gap value를 간단히 (array.length / 2)로 계산하기로 한다. 즉 첫번째 반복에서는 gap value가 3이다. 

원칙은 다음과 같다. 변수 i, j와 newElement를 만들고, 

• i = gap
• j = i(초기), 진행함에 따라 j = j - gap
• newElement = intArray[i]
• intArray[j - gap]과 newElement를 비교!

처음 시작에서 i와 j 모두 3이고, newElement는 7이다. 

			i   j
20	35	-15	7	55	1	-22

다음, newElement(→7)와 intArray[0; j에서 gap을 뺀 값](→20)을 비교한다. 20이 더 크니까 j의 위치로 shift한다.

j			i
20	35	-15	20	55	1	-22

이제 j가 0인데, 배열의 맨 앞까지 왔으므로, newElement를 j 위치에 놓는다.

j			i
7	35	-15	20	55	1	-22

다음 반복으로 진행한다. i와 j 모두 4이고, newElement는 55다.

				i   j
7	35	-15	20	55	1	-22

newElement(→55)와 intArray[1](→35)을 비교했더니 바꿀 필요가 없다.

	j			i
7	35	-15	20	55	1	-22

다음 반복으로 진행한다. i와 j 모두 5이고, newElement는 1이다.

					i   j
7	35	-15	20	55	1	-22

newElement(→1)와 intArray[2](→-15)를 비교했더니 역시 바꿀 필요가 없다. 

		j			i   j
7	35	-15	20	55	1	-22

다음 반복으로 진행한다. i와 j 모두 6이고, newElement는 -22다. 

						i   j
7	35	-15	20	55	1	-22

newElement(→-22)와 intArray[3](→20)을 비교했더니, 20이 더 크므로 20을 j의 위치로 shift한다.

			j			i
7	35	-15	20	55	1	20

 

j = j - gap 이므로, 이제 j는 3이다. newElement인 -22와 intArray[0; j - gap]을 비교했더니 7이 더 크니까, 7을 j의 위치로 shift한다.

			j			i
7	35	-15	7	55	1	20

이제 j가 0이다. j의 위치에 newElement를 놓는다.

j						i
-22	35	-15	7	55	1	20

gap value가 3일 때의 모든 반복을 마쳤다. 처음에 정한 gap value 계산식에 의하면, 다음 gap value는 1이다. 즉 이제 삽입 정렬만 하면 된다는 뜻이고, 아무 것도 하지 않은 초기의 정렬에 비해 어느 정도 정렬이 되어 있는 상태이므로, 좀 더 빠르게 삽입 정렬을 수행할 수 있을 것이다.

---

셸 정렬 주요 사항

• In-place algorithm (제자리 정렬)
  
• 시간 복잡도: gap에 따라 바뀔 여지가 많아서 확실하게 단정짓기는 어렵다. 최악의 경우는 O(N^2)이지만 보통은 훨씬 낫다.
• Unstable algorithm (불안정적)
  바로 옆의 요소끼리 교환하지 않으므로 불안정적인 상황이 발생할 수 있다.

public class Main {
    public static void main(String[] args) {
       int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

       // gap의 초기값 설정, gap이 0보다 클 때까지 반복(마지막 단계는 gap이 1이 되고, 즉 삽입정렬 시행)
        for (int gap = intArray.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < intArray.length; i++) {
                // i에 있는 값을 newElement에 삽입
                int newElement = intArray[i];
                // j의 초기값
                int j = i;

                // j는 gap보다 크거나 같아야 한다. 그렇지 않으면 j에서 gap을 뺐을 때 인덱스가 0보다 작게 된다.
                // AND, (j-gap)에 있는 값이 newElement보다 크면
                while (j >= gap && intArray[j - gap] > newElement) {
                    // j 위치로 shift
                    intArray[j] = intArray[j - gap];
                    // j에서 gap만큼 뻼
                    j -= gap;
                }

                // gap보다 작아진 j의 위치(배열의 앞쪽)에 newElement 삽입
                intArray[j] = newElement;
            }
        }

        // Print out the array
        for (int i = 0; i < intArray.length; i++) {
            System.out.print(intArray[i] + " ");
        }
    }
}

만약 while loop을,

while (j >= gap) {
    if (intArray[j - gap] > newElement)
        intArray[j] = intArray[j - gap];
    j -= gap;
}

이렇게 한다면 문제가 된다. intArray[j - gap]이 newElement보다 크지 않아도, 즉 shift 조건을 만족하지 않아도 j는 무조건 gap만큼 감소하게 되고, while loop이 끝나면 j 자리에 newElement가 삽입되므로 결과적으로 출력되는 배열값이 이상해진다. 

shift 조건을 만족하지 않으면 while loop 종료 후 intArray[j] = newElement을 수행할 때 아무런 변화가 없어야 하는데, 이를 위해선 반드시 shift 조건을 만족할 때만 j값이 감소되도록 설계 해야 하는 것이다.