앞서 포스팅한 세 가지 단순 정렬(버블, 선택, 삽입)의 시간 복잡도는 모두 O(n^2)이었다.
1만개를 정렬하는데 1초가 걸렸다면 10만개를 정렬하는데 100초가 걸린다는 뜻이다.
앞으로의 포스트에서는 이들을 개선하여 사용 해 보자.
셸 정렬
셸 정렬이란? 단순 삽입 정렬의 장점을 살리고 단점을 보완한 알고리즘으로 'Donald L. Shell'가 처음 제안하여 셸 정렬이라 부른다.
참고로 단순 삽입 정렬과는 달리 멀리 떨어져 있는 요소를 교환하므로 안정적인 정렬 알고리즘이 아니다.
단순 삽입 정렬의 특징 살펴보기
일단 셸 정렬은 단순 삽입 정렬의 확장영역이니 단순 삽입 정렬의 특징부터 알아보자.
int[] arr = {1,2,3,4,5,0,6};다음과 같은 배열로 단순 삽입 정렬을 수행한다고 가정해보자.
2번째 요소인 2부터 선택해서 정렬을 수행한다. 그러나 1,2,3,4,5는 이미 정렬된 상태이기에 요소를 이동하지는 않는다. 그렇기에 5까지는 빨리 정렬할 수 있다. 하지만 0을 대입하게 되면 0을 대입하기 위해 5,4,3,2,1을 모두 한칸씩 이동해야하고 마지막 첫뻔째 요소에 옮기는것 까지 총 6번의 이동이 필요하게 된다.
이 예시는 단순 삽입 정렬의 아래와 같은 특징을 잘 보여주는 예시라고 볼 수 있다.
A 정렬이 됐거나 또는 그 상태에 가까우면 정렬 속도가 매우 빠름.(장점)
B 삽입할 곳이 멀리 떨어지면 이동하는 횟수가 많아짐.(단점)
셸 정렬 알아보기
따라서 우리가 셸 정렬의 큰 틀을 추측해 볼 수 있다.
바로 위에서 언급한 A를 극대화시키고, B를 보완한 정렬인 것이다.
방법은 이렇다 먼저 일정한 간격으로 서로 떨어져 있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고, 간격을 좁혀 그룹의 수를 줄여가며 정렬을 반복하여 오소의 이동 횟수를 줄이는 방법이다.
※ 토니호어의 퀵 정렬이 1959에 나오기 이전에는 셸 정렬이 최고 빠른 알고리즘으로 알려져 있었다.
실제 성능은 빠른편이며 힙 정렬에 버금가는 정도로 알려져 있다.
아래서 살펴 볼 4-정렬, 2-정렬등 간격을 선택해야하는데 해당 간격을 잘 선택했을 경우 복잡도를 O(n^(1.25~1.33))도 가능하다고 한다.
하지만 일반적인 데이터 크기에 모두 적용 가능한 복잡도는 아니다.
(껍질 정렬이라고 부르는 경우는 오역이다. 껍질로서의 shell아닌 사람이름이기에)
int[] arr = {8,1,4,2,7,6,3,5};위와 같은 배열이 있다고 가정하자. 먼저 4칸 떨어져 있는 요소를 모아 배열을 4개의 그룹({8,7}, {1,6}, {4,3}, {2,5})으로 나누고 각 그룹 별로 정렬을 실시한다.
8은 7보다 크기에 둘이 위치를 교환한다.
int[] arr = {7,1,4,2,8,6,3,5};1과6은 교환할 필요가 없고, 4와3은 교환을 해야한다.
또 2와5는 교환할 필요가 없다.
int[] arr = {7,1,3,2,8,6,4,5};이렇게 4칸 떨어진 요소를 하나의 그룹으로 묶어 정렬하는 방법을 '4-정렬' 이라고 한다.
어떤가? 이렇게 4-정렬을 하고 난 후 초기 배열보단 확실히 정렬이 된 느낌이다.
이제 4-정렬을 끝내고 2-정렬을 해 보자. '2-정렬'은 2칸 떨어진 요소를 모아 두 그룹으로 나누어 정렬하는 과정이다.
{7,3,8,4}, {1,2,6,5}로 나누어지고, 각각의 그룹을 정렬하면
{3,4,7,8}, {1,2,5,6}이 된다. 2칸씩 떨어진 요소로 그룹화 했으니 아래처럼 정렬이 될 것이다.
int[] arr = {7,1,3,2,8,6,4,5};
// 2-정렬
int[] arr = {3,1,4,2,7,5,8,6}; // 2-정렬 끝초기 배열과 비교하면 작은수는 앞으로, 상대적으로 큰 수들은 뒤로 옮겨진것을 확인할 수 있다.
마지막으로 '1-정렬'을 적용하면 셸 정렬이 끝난다.
A : 8 │ 1 │ 4 │ 2 │ 7 │ 6 │ 3 │ 5 │ - 초기 배열
↓ 4개 그룹에 4-정렬을 수행한다 - 4회 정렬
B : 7 │ 1 │ 3 │ 2 │ 8 │ 6 │ 4 │ 5 │ - 4-정렬 후
↓ 2개 그룹에 2-정렬을 수행한다 - 2회 정렬
C : 3 │ 1 │ 4 │ 2 │ 7 │ 5 │ 8 │ 6 │ - 2-정렬 후
↓ 1개 그룹에 1-정렬을 수행한다 - 1회 정렬
D : 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ - 1-정렬 후(끝)
총 7회 정렬을 수행하게 된다.
(여기서 수행하는 모든 정렬 알고리즘은 단순 삽입 정렬로 수행한다.)
이렇게 총 7회 단순 삽입 정렬을 하게 되어 어떻게 보면 더 많이 수행하는것이 아니냐? 라는 의문이 있을 수 있지만, 전체적으로 요소의 이동 횟수가 줄어들어 효율적으로 정렬할 수 있다.
예제
public class Shell {
static void shellSort(int[] a) {
for (int h = a.length / 2; h > 0; h /= 2) {
for (int i = h; i < a.length; i++) {
int j;
int tmp = a[i];
for (j = i-h; j >= 0 && a[j] > tmp; j -= h)
a[j+h] = a[j];
a[j+h] = tmp;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수: ");
int[] x = new int[sc.nextInt()];
for (int i = 0; i < x.length; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
shellSort(x);
System.out.println("셸 정렬을 이용해 정렬 완료");
for (int i = 0; i < x.length; i++) {
System.out.println("x[" + i + "]=" + x[i]);
}
}
}헷갈릴 수 있는 부분 : shellSort()메서드의 3번째 for문의 증감식에서 j -= h가 된 후 아래 a[j+h] = tmp; 부분을 수행한다. 이 때 j는 -값일 수 있다.(만약 h가 3이고 j가0이었다면 -3인 상태로 for문을 탈출하는 것임) 위 방식을 응용해서 3-정렬이라면 0,3인덱스가 묶여 서로 위치를 바꾸거나(j >= 0 && a[j] > tmp;를 통과시), 바꾸지 않는다.
위 코드에서 단순 삽입 정렬을 수행하는 부분은 이전 포스트의 단순 삽입 정렬과 거의 같다. 차이점은 선택한 요소와 비교하는 요소가 서로 이웃하지 않고 h칸 만큼 떨어져 있다는 점이다. 이때 h의 초깃값은 n/2이다. for문으로 반복을 수행할 때 마다 h를 2로 나누어 절반을 만든다.
증분값(h값) 선택
앞의 설명, 코드에서는 증분값으로 4 → 2 → 1을 선택했다.
h값은 n부터 감소시켜 마지막에 1이 되면 된다. 그러면 h값(증분값이 간격)을 어떤 수열로 감소시켜야 효율적인 간격선택이 될까?
int[] arr = {8,1,4,2,7,6,3,5};배열 arr가 학생 8명의 점수를 나타낸 배열이라고 보자.
4-정렬을한다고 생각해 보자 처음 4개의 그룹으로 나뉠것이다.
{8,7} {1,6} {4,3} {2,5}
4-정렬을 하고 난 배열은 아래와 같을것이다.
int[] arr = {7,1,3,2,8,6,4,5};그 후, 2-정렬을 한다고 해 보자. 아래처럼 2그룹으로 나뉠 것이다.
{7,3,8,4}, {1,2,6,5}
문제점이 보이는가? 4-정렬때 그룹으로 묶여있던 요소들이 2-정렬에도 묶여있다.
이렇게 되면 기껏 그룹을 나눴지만 같은 멤버로 구성된 그룹만을 계속 정렬하는 셈이 된다.
이런 문제를 해결하기 위해서는 줄어드는 h값이 서로 배수가 되지 않도록 만들어야 한다. 이렇게 하면 요소가 충분히 섞여 효율적으로 정렬이 가능하다.
h= ... → 121 → 40 → 13 → 4 → 1
h값은 1부터 시작하여 x3+1로 점점 증가하는 수열을 사용하면 좋다.
수정 후 예제
shellSort()부분을 아래와 같이 바꾸어보자.
static void shellSort(int[] a) {
int h;
int lng = a.length;
for (h = 1; h < lng; h = h * 3 + 1) {} // ───────────── 1
for( ; h > 0; h /= 3) // ──────────────────────────────── 2
for (int i = h; i < lng; i++) {
int j;
int tmp = a[i];
for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j+h] = a[j];
a[j+h] = tmp;
}
}1로 표기한 부분은 h의 초기값을 구하는 부분이다. 1부터 시작하여 값을 3배하고 1을 더하면서 n을 넘지 않는 가장 큰 값을 h에 대입해준다.
2로 표기한 부분에서 초기 버전과 다른점은 h값이 변하는 방법이다.(반복할 때마다 h값을 3으로 나눔)반복하여 마지막에 h값은 1이 된다.
※ 요솟수가 7일때 초기값은 4가된다. 실질적으로 셸 정렬이 아닌 단순 삽입 정렬이 실행되게 될 수도 있다.
