단순 삽입 정렬

셸 정렬

• 삽입 정렬을 보완한 알고리즘

삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안

삽입 정렬 장점

정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.

삽입 정렬의 최대 문제점:

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

- 요소들이 삽입될 때, 이웃한 위치로만 이동
즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다
https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html

• 단순 삽입 정렬의 장점을 살리고, 단점을 보완한 정렬 알고리즘
• 도널도 셸(D.L. Shell)이 고안
• 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입정렬을 수행하고,
  그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법

셸 정렬의 시간 복잡도

멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않음
O(n1.25)

셸 정렬 방법

삽입정렬과 셸 정렬의 차이점

선택한 요소와 비교하는 요소가 서로 이웃하지 않고, h칸 만큼 떨어져 있다.

/* 셸 정렬 */
#include <stdio.h>
#include <stdlib.h>

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

int main(void)
{
	int i, nx;
	int *x;				/* 배열의 첫 번째 요소에 대한 포인터 */
	puts("셸 정렬");
	printf("요소 개수 : ");
	scanf("%d", &nx);

	x = calloc(nx, sizeof(int));
	for (i = 0; i < nx; i++) {
		printf("x[%d] : ", i);
		scanf("%d", &x[i]);
	}

	shell(x, nx);			/* 배열 x를 셸 정렬 */

	puts("오름차순으로 정렬했습니다.");
	for (i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);

	free(x);				/* 배열을 해제 */

	return 0;
}

셸 정렬 버전2

증분 값(h값)의 선택

• 요소가 충분히 섞일 수 있도록 h 값이 서로 배수가 되지 않도록 함
  h = …, 121, 40, 13, 4, 1

• 1부터 시작하여 3배한 값에 1을 더한 수열 [h = 3 x h + 1]

• h의 초기 값은 너무 크면 효과가 없기 때문에 배열의 요소 개수 n을 9로 나눈 값을 넘지 않도록 정함
  

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

/*--- 셸 정렬 함수 (버전 2 : h = …, 13, 4, 1) ---*/
void shell(int a[], int n)
{
	int i, j, h;
	for (h = 1; h < n / 9; h = h * 3 + 1)
		;
	
	for (; h > 0; h /= 3)
		for (i = h; i < n; i++) {
			int tmp = a[i];
			
			for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
				a[j + h] = a[j];
			a[j + h] = tmp;
		}
}

int main(void)
{
	int i, nx;
	int *x;				/* 배열의 첫 번째 요소에 대한 포인터 */

	puts("셸 정렬");
	printf("요소 개수 : ");
	scanf("%d", &nx);
	x = calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++) {
		printf("x[%d] : ", i);
		scanf("%d", &x[i]);
	}

	shell(x, nx);			/* 배열 x를 셸 정렬 */

	puts("오름차순으로 정렬했습니다.");
	for (i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);

	free(x);				/* 배열을 해제 */
	
	return 0;
}