쉘정렬은 지금까지 배운 정렬과 좀 다른 방식으로 생각해 봐야 한다. 쉘 정렬은 다양한 해석이 있는데, 그 이유는 내부에 사용되는 알고리즘으로 삽입정렬을 많이 사용하는데, 버블정렬이나 선택정렬 등도 사용 해도 되기 때문이다. 보통 삽입정렬로 설명하는데, 그 이유는 효율이 좋기 때문에 그렇다. 어떻게 내부에서 선택되는 알고리즘이 다양해 질 수 있는지 알기 위해서 쉘정렬의 구조를 파악해야 하는데 개념 자체는 어렵지 않다. 개인적인 의견으로는 이런 구조로 인해서 쉘정렬이라고 하면 어떤 형식의 알고리즘이 사용되었는지 기술해 주는 정도는 필요하다고 생각한다.
쉘 정렬
위 배열은 14개의 요소를 지닌 배열이다. 쉘정렬은 주어진 자료를 다음과 같은 형식으로 나누어 생각한다.(나누는 방식은 다양할 수 있다. 여기서 나누는 방식은 가장 간편한 방식, 2, 4, 8, ...)
여기서는 다음 한가지만 기억하고 넘어가자. 마지막 각 요소 개수(16)만큼 나눈 경우 개로 나눈 경우만 가지고도 정렬은 가능하다.
그러면 2, 4, 8 씩 나누어 생각하는 이유는 무얼까? 그 이유는 정렬을 효율적으로 만들기 위해서다.
쉘정렬을 좀 더 살펴보자.
2 부분으로 나눈 후 각 부분의 요소 번호가 같은 것 끼리 묶는다. {10,3}, {13, 1}, {6, 11}, {8, 4}, {2, 14}, {9, 5}, {3, 12} 이렇게 다섯 개의 배열이 생기면 각 배열을 정렬하면 된다. 정렬하는 방법은 처음에 말한 것처럼 여러가지가 있을 수 있다.(섞어 사용할 수도 있음.)
아무튼 정렬을 하면 다음과 같이 정렬된다.
다음은 4부분으로 나뉜 경우인데
마지막 9,12까지 포함하여 5부분이 된다. 14개의 자료를 4로 나누면 몫이 3이 된다. for문으로 각 부분의 첫 번째 인덱스(요소)를 선택하려면 전체 배열의 첫 번째 인덱스 0에서 3식 더해가야 한다.
이렇게 다음과 같은 배열로 묶어서 생각한다.(요소 번호가 같은 것 끼리) {7, 4, 3, 11, 9}, {1, 2, 10, 8, 12}, {6, 5, 13, 14}
각 배열을 정렬하면
다시 8부분으로 나누고 {3, 5, 2, 7, 13, 10, 11}, {1, 4, 6, 8, 9, 14, 12} 의 배열로 나누어 생각한다.
이젠 마지막으로 각 요소별로 나눈 경우인데 이 경우는 하나의 배열 즉 전체 배열을 정렬하는 의미와 같다.
여기서 {2,1,3,4,5,6,7,8,10, 9, 11, 12, 13, 14}를 정렬만 하면 되는데 잘 보면 완전하지는 않지만 대부분 순서대로 정렬되어 있음을 알 수 있다.
따라서 쉘정렬에서 마지막으로 이루어지는 정렬은 수행시간이 매우 짧아진다.
마지막 정렬은 2, 1의 순서와 10, 9의 순서만 바꾸게 된다.
쉘정렬 코드
사실 쉘정렬의 개념은 간단하지만 알고리즘을 어떻게 짜느냐에 따라서 다양한 형태로 나올 수 있다. 여기서는 쉘정렬에서 효율이 좋다는 삽입정렬을 이용해 보겠다. 삽입정렬이 어떤 식으로 이루어지는지는 꼭 먼저 익혀두자. 너무 어렵다면 버블정렬로 도전해보면 매우 쉽다.
삽입정렬
쉘정렬에 삽입정렬을 단순히 복사 붙여넣기를 한 후 몇 가지만 고쳤다.
쉘정렬
우선 gap은 각 묶음에서 같은 요소 번호 간의 간격이다. 이 간격이 1이 될 때까지 정렬을 하는데 gap을 선택하는 방법은 다양하지만 가장 효율적인 방법은 gap = 3*n+1; 인 경우(n=0,1,2,3,4,...)라고 한다. 따라서 gap은 1, 4, 13, 40, 121이 되는데 처음에 제일 큰 gap을 구한 후 3으로 나누면서 gap을 구하면 된다.
gap이 정해지면 gap크기 만큼의 묶음의 수가 생긴다. 따라서 z는 각 묶음의 요소 번호를 의미하기도 한다.
각 묶음의 요소 번호끼리 묶은 것을 정렬하기 위해서 삽입 정렬 알고리즘을 붙여 넣는다.
삽입정렬에서 +1만큼 요소를 이동하지만, 여기서는 gap만큼 이동해야 한다. 이에 맞춰 수정하면 쉘정렬을 완성할 수 있을 것이다.