Chap 6-4. 쉘 정렬(Shell Sort)

🌈Shell 정렬이란?

쉘은 ‘Donald L. Shell’이 제안한 방법으로 “쉘 정렬”이라고 한다.

다른 정렬 방법들은 정렬 방식이 이름이지만 이것은 만든 사람의 이름이라는 점에서 차이가 있다. 여러 가지 정렬 방법들을 배우는데 이름과 방법이 매치가 되지 않는다. 그래서 본인은 정렬 방식이 이름에 표면적으로 드러날 수 있도록  “Gap 삽입 정렬”이라고 자의적으로 생각해봤다.(일명 뇌피셜이라 할 수 있다.. ㅎ)

 

✔️방법 : 전체 리스트를 일정 간격(gap)의 부분 리스트로 나눈다. -> 나누어진 각각의 부분 리스트를 insertion sort 수행한다. (부분 리스트 별로 sort를 수행한다)

 

🌈motivation

✔️버블 정렬이나 삽입 정렬이 수행되는 과정은 ”기껏해야” 이웃하는 원소의 자리바꾸는 것이다. 

버블 정렬의 수행 과정을 보면 가장 큰 숫자가 배열의 뒷부분으로 가는 것은 빠르지만 작은(가벼운) 숫자가 배열의 앞부분으로 매우 느리게 이동한다는 특징을 알 수 있다. 

또한, 삽입 정렬 특징을 살펴보면  마지막 원소가 가장 작은 숫자일  경우 그 숫자가 배열의 맨 앞으로 이동해야 하므로, 모든 다른 숫자들이 1칸 씩 오른쪽으로 이동해야한다. 

하지만 어느 정도 정렬된 리스트의 경우 삽입 정렬은 대단히 빠르다.

요소들이 멀리 떨어진 위치로 이동할 수 있게 하면 보다 빠르게 어느 정도 정렬된 리스트가 되며 적게 이동하여 제자리를 찾을 수 있다.

이 방법을 착안한 것이 shell정렬이라고 할 수 있다.

 

🌈아이디어

삽입 정렬을 이용하여 일반적인 정렬 알고리즘보다 배열 뒷부분의 작은 숫자를 앞부분으로 ‘빠르게’ 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 ‘빠르게’ 이동시키자.

⇒ 간격을 이용한 쉘 정렬

 

🌈예시

주어진 값 = 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80

 

[ step 1 ] 간격을 5로 하여 그룹을 나누어보자

-그룹 1 [30, 80, 50]

• 그룹 2 [60, 40, 30]

– 그룹 3 [90, 20, 40]

– 그룹 4 [10, 10, 90]

– 그룹 5 [40, 60, 80]

 

[ step 2 ]각각의 그룹끼리 삽입 정렬을 하자

한 번의 라운드만 실행해도 크게 이동하여 큰 숫자들은 뒤로, 작은 숫자들은 앞으로 가는 것을 볼 수 있다. (어느 정도 rough 하게 정렬이 된다)

⇒ 다음엔 간격을 5보다 작게 하자

 

✔️간격 3으로 하고 삽입정렬을 하자

✔️간격을 1로 하고 삽입정렬을 하자 → 반드시 간격을 1로 해서 정렬하는 것이 필요하다. 어느 그룹에도 속하지 않는 숫자가 있을 수 있기 때문이다.

**모든 원소를 1개의 그룹으로 여기는 것은 “삽입 정렬” 그 자체라고 볼 수 있다. 삽입 정렬은 정렬 이전 숫자들의 정렬 상태가 어느 정도 되어 있으면 성능이 뛰어난다. 간격 1이되기까지 단계를 거치면서 어느 정도 정렬되었기 때문에 빠른 정렬이 가능하다. 

 

🌈 적당한 간격이란?

(간격을 줄일 때 5, 4, 3,2, 1 보다는 5, 3, 1로 줄이는 것이 좋다 ,일반적으로 홀수 간격을 준다. )

홀수일 때 더 효율적이라고 알려져 있다.

gap을 계산하기 위해 n/2를 했을 때 짝수가 나온다면 +1을 하여 홀수로 만들어준다.

 

🌈 의사코드

입력: 크기가 n인 배열 A
출력: 정렬된 배열 A

1. for each gap h = [ h0>h1>...>hk=1] // 큰 gap부터 차례로
2.   for i = h to n-1 //갭 위치부터 배열의 하나 전까지 차례로 증가하면서 
3.         CurrentElement = A[i] 
4.         j = i //i와 j는 같은 곳을 가리킴 
5.        while (j >= h) and (A[j-h] > CurrentElement) //간격만큼 왼쪽으로 떨어져있는 것과 비교
//d앞에 있는 것이 뒤에 있는 것보다 크다면
6.              A[j] = A[j-h] //위치 교환 
7.               j = j-h //간격만큼 앞쪽으로 이동 
8.         A[j] = CurrentElement
9. return A

🌈 코드 구현

#include <stdio.h>
#include <stdlib.h>

#define N 15

void shellSort(int A[])
{
	int currentElement;

	printf("Before Sort : ");
	for (int j = 0; j < 0; j++) //배열 출력 
		printf("%d", A[j]);
	printf("\\n");

	printf("\\n <<<<<<<<<<<<<<<<< Shell Sorting .... >>>>>>>>>>>>>>>>>>\\n");
	for (int h = 5; h >= 1; h -= 2) //gap = 5라면, gap은 5, 3, 1순으로 줄어든다. 
	{
		for(int i = h; i <= N-1; i++)//오른쪽으로 한칸씩 가면서 
		{
	
				currentElement = A[i];
				int j = i; //처음 시작은 일단 같은 i와 j 가 같은 곳을 가리킴 

				while(j >= h && A[j-h] > currentElement) //j가 간격 시작보다 작을 때까지 반복
				{
					A[j] = A[j-h];
					j -= h;
				}
				A[j] = currentElement;
			}

			printf(" Gap %d >>", h);
			for (int j = 0; j < N; j++)
			{
				printf("%d", A[j]);
			}
			printf("\\n");
		
	}

}

int main()
{
	int A[N] = {30, 60, 90, 10, 40, 80, 40, 20, 10, 60, 50, 30, 40, 90, 80};
	shellSort(A);
	return 0;
}

 

코드 중 for문에 대해서 자세히 살펴보자 

for(int i = h; i <= N-1; i++)
			{
				currentElement = A[i];
				int j = i; //처음 시작은 일단 같은 i와 j 가 같은 곳을 가리킴 

				while(j >= h && A[j-h] > currentElement) //j가 간격 시작보다 작을 때까지 반복
				{
					A[j] = A[j-h];
					j -= h;
				}
				A[j] = currentElement;
			}

이 부분은 for-루프에서 간격 h에 대해 그룹 별로 삽입 정렬이 수행되는데, 실제 자리바꿈을 위한 원소 간의 비교는 아래와 같은 순서로 진행

[while 문 조건 중 " j >= h " 부분은 ]

shell 알고리즘은 삽입정렬을 이용하므로 뒤에서부터 앞으로 진행하며 삽입될 위치를 선정한다는 것을 유의하자.

이 부분은 앞에 더 비교할 원소가 있는 지 확인하는 것이다.

🌈시간복잡도

쉘 정렬의 시간 복잡도는 사용하는 간격에 따라 분석해야 한다.(간격에 따라 달라진다)

 

최악 경우 시간 복잡도: 히바드(Hibbard)의 간격

– 2k-1 (2k-1, ⋯, 15, 7, 5, 3, 1)을 사용하면, O(n^1.5) 지금까지 알려진 가장 좋은 성능을 보인 간격은 다음과 같다.

– 1, 4, 10, 23, 57, 132, 301, 701, 1750 (Marcin Ciura)

• 쉘 정렬의 시간 복잡도는 아직 풀리지 않은 문제라고 할 수 있다. – 시간복잡도를 알아내기 위해서는 가장 좋은 간격을 알아내야 하는 것이 선행되어야 하기 때문이다.

 

🌈쉘 정렬의 특성

-쉘 정렬은 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보인다. (시간복잡도가 거의 일차식)

-불연속적인 부분 리스트(gap만큼 떨어진)에서 원거리 자료 이동으로 보다 적은 위치 교환으로 제자리를 찾을 가능성이 증대한다.

-부분 리스트가 점진적으로 정렬된 상태가 되므로 insertion sort 속도가 증가한다.

-쉘 정렬은 임베디드 시스템에서 주로 사용한다. 

쉘 정렬의 특징인 간격에 따른 그룹 별 정렬 방식이 H/W 로 정렬 알고리즘을 구현하는데 매우 적합하다.