셸 정렬

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

삽입정렬

장 - 어느정도 정렬 된 배열은 넘어가며 빠르게 완성

단 - 이웃한 위치로만 이동하기에 가야할 위치가 멀면 많은 이동을 해야함(오래걸림)

 

 

1.배열을 일정한 기준으로 분류함. (위 사진의 경우는 간격 3)

2.부분 배열을 생성

3.각 부분배열을 삽입정렬로 정렬

4.부분 정렬 완료 후 배열을 더 적은 수의 부분배열로 만들고 반복한다.

5.부분리스트가 1개가 되면 완성

 

간격 초깃값은 배열크기/2 로 한다. 생성된 부분배열은 간격값과 같음.

회전마다 간격을 절반으로 한다. 간격은 홀수로 하는게 좋고 짝수가 된다면 +1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<string.h>
void insert(int a[], int first, int last, int gap);
void shell(int[], int num);
int main() {
	int x[10];
	for (int i = 0; i < 10; i++)
	{
		scanf("%d", &x[i]);
	}
	shell(x, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", x[i]);
	}
}
void insert(int a[], int first, int last, int gap)
{
	int j;
	int key;
	for (int i = first+gap; i < last; i = i + gap)
	{
		key = a[i];
		for (j = i - gap; j >= first && a[j] > key; j=j-gap)
		{
			a[j + gap] = a[j];
		}
		a[j+gap] = key;
	}
}
void shell(int x[], int num)
{
	int gap;
	for (gap = num / 2; gap >= 1; gap = gap / 2)
	{
		if (gap % 2 == 0)
		{
			gap++;
		}
		for (int i = 0; i < gap; i++)
		{
			insert(x, i, num , gap);
		}
	}
}

연속적이지 않은 부분 배열에서 교환이 일어나고 한번에 멀리 이동. 기존 삽입정렬보다 교환된 요소들이

최종 위치에 미리 가 있을 확률이 높음.

 

부분 배열은 정렬이 꽤 이루어진 상태이므로 마지막 부분정렬 개수가 1이 됐을 때

빠른 속도로 삽입정렬을 수행하게 된다.

 

시간복잡도

최선 O(n)

평균 O(n^1.5)

최악 O(n^2)

평균 O(n^2) 였던 삽입정렬에서 개선됨.