정렬 알고리즘4 - 셸 정렬(Shell Sort)

출처- 위키백과

셸 정렬(Shell Sort)

작동방식

정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입정렬을 실시한 뒤 그룹을 합치면서 정렬을 반복하면서 요소의 이동횟수를 줄이는 방법

 

 

특징

• 삽입정렬의 단점은 보완하고 장점은 살린 정렬 방법
• (삽입정렬의 단점은 삽입할 위치가 멀리 떨어진 경우 요소를 이동시키는 거리가 길다는 것이다. 삽입정렬의 장점은 정렬된 상태에 가까워질수록 정렬시키는 속도가 더욱 빨라진다는 것이다)
• 셸정렬은 그룹별로 미리 몇차례 정렬을 해둔뒤에 삽입정렬을 실시해 삽입정렬의 장점을 취하는 정렬방법이다.
• 셸정렬을 실시하면 정렬해야하는 횟수는 증가하지만 요소이동 횟수가 줄어들어 보다 효율적인 정렬이 가능하다.

 

 

 

정렬되는 모습 살펴보기

정렬할 요소는 [6, 2, 5, 3, 1, 7, 4, 8], 이렇게 숫자 8개이다.

먼저 그룹별로 몇차례 정렬을 해주도록 한다. 

정렬할 요소의 개수가 8이므로 1/2인 4만큼 떨어진 요소끼리 정렬한다

(그룹별 요소는 2개, 그룹 개수 4개)

 

 

 

 

그룹별로 정렬하기

 

 

 

 

 

다시 1/2를 줄여 2만큼 떨어진 요소끼리 정렬한다

(그룹별 요소는 4개, 그룹 개수 2개)

 

 

 

 

정렬하기

 

 

 

마지막으로 1/2를 줄여 1만큼 떨어진 요소끼리 정렬을 완료한다

(그룹별 요소는 8개, 그룹 개수 1개)

 

 

---

 

구현코드- Java

    public void sort(int[] a){
        int n = a.length;
        int i;		//반복자1
        int j;		//반복자2
        int tmp;	//임시로 값을 받는 변수
        int h;		//감소값. 1/2씩 감소되도록 설정
        for(h=n/2; h>0; h/=2){
            for (i=h; i<n; i++) {
                tmp = a[i];
                for (j = i-h; j >= 0 && a[j] > tmp; j-=h) {
                    a[j + h] = a[j];
                }
                a[j + h] = tmp;
            }
        }
    }

 

 

---

증분값 정하기

 

 

참고로 위에서는 감소되는 값을 1/2 로 지정해 나누어 떨어지는 수로 설정하였다. 사실 보다 효율적인 그룹나누기를 하기 위해서는 서로 배수가 되지 않는 것이 좋다.

 

왜냐하면 첫번째 그룹 나누기를 하면 아래와 같이 나누어진다

[6, 1]
[2, 7]
[5, 4]
[3, 8]

 

이어서 두번째 그룹 나누기를 하면 아래와 같다
[1, 4, 6, 5]
[2, 3, 7, 8]

 

색깔이 나눠진 것을 보니 그룹 나누기를 할때 무작위로 잘 섞이지 않고 규칙적으로 섞인 것을 알 수 있다.

셸정렬은 삽입정렬 실시전 어느정도 예비 정렬을 하는 것이 목적이므로 전체적으로 잘 섞여야 좋은 효율을 기대할 수 있다.

 

 

예를 들어 증분값 h 는 아래와 같이 지정하면 효율적인 결과를 얻을 수 있다

h = ..., 121, 40, 13, 4, 1

위 수열은 n값의 3배에 1을 더한 값이다. 서로 배수가 되지 않는 값이다

 

위키백과를 보면 1, 5, 12, 23, 62, 145, 367, 815, 1968, 4711, 11969, 27901, 84801, 213331, 543749 등의 숫자가 제시된다.

 

또한 증분값의 초깃값이 너무 크지 않은 것이 좋다. 증분값이 크다면 각 그룹의 요소개수는 적고 전체 그룹 개수는 많아지기 때문이다. 적당한 증분값을 지정해 그룹의 요소개수와 전체 그룹의 개수를 조정하는 것이 좋다. 예를들어 배열 요소 개수 n을 9로 나눈 n/9 의 값을 넘지 않도록 지정한다.

 

---

개선한 셸정렬 코드

public void sort(int[] a){
	int n = a.length;
	int i;      //반복자1
	int j;      //반복자2
	int tmp;    //임시로 값을 받는 변수
	int h; //감소값. 예제에서는 1/2 씩 감소하도록 설정함
	
    //h 의 초깃값 구하기
	for(h=1; h<n/9; h=h*3+1)
		;
	for(; h>0; h/=3){
		for (i=h; i<n; i++) {
			tmp = a[i];
			for (j = i-h; j >= 0 && a[j] > tmp; j-=h) {
				a[j + h] = a[j];
			}
			a[j + h] = tmp;
		}
	}
}