6-5장 쉘 정렬

1. 단순 삽입 정렬의 특징 이해하기 

 

- 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라짐 (장점)

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

 

 

2. 쉘 정렬 살펴 보기 

 

- 단순 삽입 정렬의 장점은 살리고 단점은 보완한 알고리즘 

- 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬 수행

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

 

- ex) 배열 {8,1,4,2,7,6,3,5}을 4개의 배열로 나누기 

 - ({8,7},{1,6},{4,3},{2,5})

 - 4- 정렬 

 

 

- 2-정렬 ({7,3,8,4},{1,2,6,5}) 

 

 

- 1-정렬을 적용하면 정렬을 마치게 됨 

 

- h-정렬

 -> 쉘 정렬 과정에서 수행하는 각각의 정렬 

 

1) 2개의 요소에 대해 '4-정렬'을 한다(4개의 그룹)

2) 4개의 요소에 대해 '2-정렬'을 한다(2개의 그룹)

3) 8개의 요소에 대해 '1-정렬'을 한다 (1개의 그룹) 

-> 총 7회 

-> 정렬해야하는 횟수는 늘지만 전체적으론느 요소 이동의 횟수가 줄어들어 효율적인 정렬 가능

 

- 쉘정렬 

 - 삽입정렬과 유사하나 선택한 요소와 비교하는 요소가 서로 이웃하지 않고 h만큼 떨어져 있음

// 쉘 정렬  
#include <stdio.h> 
#include <stdlib.h>

//쉘 정렬 함수 
void shell(int a[], int n) 
{
	for(int h=n/2; h>0; h/=2)
		for(int i=h; i<n; i++) {
			int tmp = a[i];
			int j;
			for(j=i-h; j>=0 && a[j]>tmp; j-=h)
				a[j+h] = a[j];
			a[j+h] = tmp;
		}
}

int main()
{
	int nx;
	puts("쉘 정렬");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x = (int *)calloc(nx,sizeof(int));
	for(int i=0; i <nx; i++) {
		printf("x[%d]:", i);
		scanf("%d",&x[i]);
	}
	shell(x,nx); //배열 x를 쉘 정렬
	puts("오름차순으로 정렬했습니다.");
	for(int i=0; i<nx; i++)
		printf("x[%d]=%d\n", i, x[i]); 
	free(x); //배열을 해제 
	
	return 0; 
}

 

2.1 증분값(h값)의 선택 

 

- h값이 서로 배수가 되지 않도록 해야함 

 

ex) 1부터 시작하여 3배한 값에 1을 더하는 수열

// 쉘 정렬 (버전 2: h=..,13,4,1) 
#include <stdio.h> 
#include <stdlib.h>

//쉘 정렬 함수 
void shell(int a[], int n)
{
	int h;
	for(h=1; h<n; h=h*3+1);
	for(;h<0; h/=3)
		for(int i=h; i<n; i++) {
			int tmp=a[i];
			int j;
			for(j=i-h; j>=0 && a[j]>tmp; j-=h)
				a[j+h] = a[j];
			a[j+h] = tmp;
		}
}

int main()
{
	int nx;
	puts("쉘 정렬");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x = (int *)calloc(nx,sizeof(int));
	for(int i=0; i <nx; i++) {
		printf("x[%d]:", i);
		scanf("%d",&x[i]);
	}
	
	shell(x,nx); //배열 x를 쉘 정 렬 
	 
	puts("오름차순으로 정렬했습니다.");
	for(int i=0; i<nx; i++)
		printf("x[%d]=%d\n", i, x[i]); 
	free(x); //배열을 해제 
	
	return 0; 
}

 

- 시간 복잡도 O(n^1.25)