(C/C++) 정렬 - 쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

안녕하세요.

오늘은 쉘 정렬에 대해서 알아보겠습니다.

 

1. 쉘 정렬(Shell Sort)이란?

삽입 정렬에 경우 정렬되어 있을 수록 빠르고 역순일 경우 느린데

이를 보완 하기 위해 나온 정렬 입니다.

다만 산입정렬은 안정성이 있고 쉘정렬은 안정성이 없다 라는

차이점이 있습니다.

삽입 정렬의 경우 인접한 숫자와 비교 후 위치를 바꾸는데 

역순일 경우 작은 값이 맨 뒤에 있기때문에 n 번의 비교와 이동을 하게 됩니다.

쉘 정렬은 이를 보완하기 위해서 인접요소가 아닌 일정 간격끼리 비교를 합니다.

간격(h) 가 10 이라면 0 10 20 30 끼리 1 11 21 31 끼리 2 12 22 32 끼리 정렬 후

h의 간격을 줄여서(예시로 /2) 0 5 10 15 20 25 30 35, 1 6 11 16 21 26 31 36 정렬하고 

또 간격을 줄이고 정렬...h 가 1이 될때까지 진행되는 정렬입니다.  

 

2. 쉘 정렬의 특징

기본적으로 삽입 정렬과 비슷하다.

안정성 X

최선의 경우 O(N) 일반적인 경우 O(N^1.5)  최악의 경우 O(N²) 의 시간복잡도

인접한 요소를 교환하는 삽입 정렬의 단점을 극복하기 위해 만들어졌기 때문에

특정 간격의 요소를 뽑아서 정렬 한다.

간단하고 빠르기 때문에 많이 사용하는 정렬 중 하나 

 

정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh)

 

3. 쉘 정렬의 구현

void ShellSort_1(int _arrays[], int _arraysLength)
{
	for (int h = _arraysLength / 2; h > 0; h /= 2)	//간격은 배열 길이의 절반 
	{
		for (int i = 0; i < h; i++)
		{
			for (int j = i + h; j < _arraysLength; j += h)
			{
				int num = _arrays[j];
				int index = j;
				while (index > h - 1 && _arrays[index - h] > num)
				{
					_arrays[index] = _arrays[index - h];
					index -= h;
				}
				_arrays[index] = num;
			}
		}
	}
}

void ShellSort_2(int _arrays[], int _arraysLength)
{
	int h;
	for (h = 1; h < _arraysLength; h = 3 * h + 1);	//제일 빠르다고 알려진 간격

	for (h /= 3; h > 0; h /= 3)
	{
		for (int i = 0; i < h; i++)
		{
			for (int j = i + h; j < _arraysLength; j += h)
			{
				int num = _arrays[j];
				int index = j;
				while (index > h - 1 && _arrays[index - h] > num)
				{
					_arrays[index] = _arrays[index - h];
					index -= h;
				}
				_arrays[index] = num;
			}
		}
	}
}

두가지 shell 정렬의 차이점은 h 의 간격 설정인데요.

어느 수학자가 3 * h + 1 의 간격이 가장 빠르다고 밝혔으며

1번 함수보다 약 20%의 속도 증가가 있다고 합니다!

감사합니다.

 

다른 정렬

버블 정렬(Bubble Sort) - 안정성 O, O(N²)

선택 정렬(Select Sort) - 안정성 X, O(N²)

삽입 정렬(Insert Sort) - 안정성 O, O(N²)

쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

병합 정렬(Merge Sort) - 안정성 O, O(N log N)

퀵 정렬(Quick Sort) - 안정성 X, O(N log N)