[알고리즘] 정렬 알고리즘 - 셸 정렬 Shell Sort

 

셸 정렬 (Shell Sort) 알고리즘 : 

삽입 정렬 의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘, 불안정 정렬.

정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입 정렬을 수행하고,

그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄임

 

삽입 정렬의 장/단점

   장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 빨라진다

   단점 : 삽입할 위치가 멀리 떨어져 있으면 이동(삽입)해야 하는 횟수가 많아진다

 

셸 정렬은 전체의 배열을 한번에 정렬하지 않고

정렬해야 할 배열을 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 그룹을 만들어 각 그룹을 삽입 정렬한다.

부분 그룹을 구성할 때 주어진 배열의 각 K번째 요소를 추출하여 만드는데, 이 K를 간격(gap)이라 한다.

각 단계별로 하나의 부분 그룹의 요소 개수는 증가, gap은 감소하며 gap이 1이 될 때 까지 반복한다.

실제로 여러개의 배열로 나누는 것이 아니라, 단순히 gap 값으로 간격을 주어 부분 그룹이 만들어진 것 처럼 구현한다.

 

삽입 정렬에 비해 정렬 횟수는 증가하지만 전체적으로는 요소의 이동 횟수가 줄어들어 더 효율적이다.

 

int shell = {8, 1, 4, 2, 7, 6, 3, 5}

1. 4칸만큼 떨어진 요소를 모아 배열을 4개의 그룹으로 나누고 각 그룹별로 삽입 정렬 ( gap = 4 )

 

배열 shell의 셸 정렬 과정 - 1

 

2. 1번 정렬을 마친 상태에서 2칸만큼 떨어진 요소를 모아 배열을 2개의 그룹으로 나누고 각 그룹별로 삽입 정렬 ( gap = 2 )

 

배열 shell의 셸 정렬 과정 - 2

 

3.  2번 정렬을 마친 상태에서 삽입정렬 ( gap = 1 )

 

shell의 경우 gap값을 4, 2, 1(gap/2)로 감소하며 7회의 정렬로 정렬을 마쳤다.

 

셸 정렬은 gap값에 따라 시간이 크게 달라지기 때문에 gap값의 설정이 중요한데

보통 셸 정렬에서 gap은 전체 배열의 요소 수 N을 2로 나누는 값으로 진행하지만, 보통 짝수보다는 홀수가 더 빠르고, 3으로 나누고 1을 더하는 경우(N/3+1)가 더 빠르다고 알려져 있다.

 

메서드 shellSort() : 길이가 n인 배열 a를 셸 정렬

매개변수 : int[] a, int n

 

- 셸 정렬

void shellSort(int[] a, int n) {
	int h = n;
	do {
		h = h/3+1;
		for(int i = h; i < n; 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;
		}
	} while(h != 1);
}

 

 

 

 

셸 정렬 Shell Sort :

최선 = O(N), 평균 = O(N^1.5), 최악 = O(N^2)

불안정한 정렬