[정렬알고리즘] Shell Sort 쉘 정렬

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 
알고리즘의 동작에 대한 분석 및 구현 코드의 설명.

Shell Sort  _  쉘 정렬

원래의 데이터를 여러 개로 분리하고, 분리된 데이터에서 삽입 정렬 하여 정렬

쉘 정렬은 삽입 정렬을 이용하여 여러 개의 서브 시퀀스로 나누어 각각 삽입 정렬을 반복하여 정렬하는 알고리즘이다. 이때 k 값을 줄여가며 여러 서브 시퀀스로 나누는데, 이 서브 시퀀스는 일정한 k 간격만큼 떨어진 원소들만 포함하여 만든다. 이때 k 값은 여러가지로 정할 수 있지만, 홀수 와 짝수가 번갈아 가면서 나오는, 증가 시에는 3*k+1, 감소 시에는 3/ k 로 감소 하는 k 값을 사용하는 것이 일반적이다. 

이렇게 서브 시퀀스로 나누는 이유는 서로 거리가 먼 원소들끼리의 비교를 미리 하여 비교 연산 횟수를 줄이기 위함이다. 예를 들어 가장 작은 원소가 가장 마지막에 있다면, 삽입정렬에서는 순서대로 정렬을 수행하기 때문에 가장 마지막에 선택되어서 앞의 데이터 들과 비교해야 하므로 오래 걸리지만, 쉘 정렬을 사용하면 전체적인 삽입 정렬을 수행하기 전에 key 값을 이용해 세부 시퀀스 들이 먼저 정렬이 수행되었기 때문에 작은 값은 앞 자리에 분포 되어있어 비교 연산 횟수가 줄어들 수 있다. 이렇게 세부 시퀀스들이 정렬을 마치게 되면 전체적으로 삽입 정렬이 이루어지고 정렬이 끝나게 된다. 

시간 복잡도는 최선의 경우에는 O(nlogn), 평균은 𝜃(n^1.25), 최악의 경우에는 O(n^2)이 나온다.

쉘 정렬에는 삽입 정렬을 사용하여 정렬하기 때문에 in-place 정렬이며, stable 한 정렬이다.

 

Implementation

Swap 함수

모든 정렬 알고리즘에서 Swap 모듈을 사용하므로, 함수화 하여 사용한다. 

동적 배열의 주소 값과 정수 값 두개를 인자로 받고 첫번째 인자 a 와 두번째 인자 b를 index 로 하는 배열의 두 값을 바꿔주는 함수이다. 

void Swap(int* arr, int a, int b){
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

Shell Sort

Shell Sort 함수가 호출되면 최대 gap값을 for문을 통해 정하게 된다. 일반적인 gap값을 정하기 위해 gap*3+1 값으로 정했다. 이 값은 Insertion Sort 함수가 수행되면 gap/3으로 줄어 들게 된다. gap 값이 0, 원소 간 간격이 0, 즉 분할된 서브 리스트가 곧 배열이 되면 삽입 정렬은 멈추게 되고, 전체적으로 정렬이 이뤄지게 된다. 

Insertion Sort 함수는 인자로 배열 크기와 gap 값을 받는다. For for문과 while문을 돌며 Gap값 차이 나는 원소들과 오름 차순으로 삽입 정렬을 수행한다. 이때 정렬이 수행되면 그 전 gap 차이 나는 원소와 도 정렬해야 하므로 gap 값을 빼주며 정렬을 수행한다.Shell 함수는 메인 함수에서 호출되며,  Shell 정렬을 시작하고, 실행시간을 측정한다. 

 

class ShellSorter{
public:
	void InsertionSort(int* arr, int n, int gap){
		for(int i = gap; i<n; i++){ //gap 차이나는 값들을 비교 정렬한다.  
			int j = i-gap; //i 와 gap 차이 나는 값
			while(j >= 0 && arr[j] > arr[j+gap]){ //0이상이고, 서로 gap차이 나는 전 값이 후 값보다 크다면 정렬 수행
				Swap(arr, j, j+gap); //큰 값을 뒤로 보낸다
				j = j-gap; //그 이전 gap 차이 나는 원소로 가서 정렬한다. 
			}
		}
	}
	void ShellSort(int *arr, int n){
		int gap; 
		for(gap = 1; gap<n; gap=3*gap+1 ); //정렬된 배열에서 첫번쨰 gap 값을 찾는다. 
		while(gap>0){ //gap 값이 0 이 될 때까지
			InsertionSort(arr, n, gap); //gap 차이나는 원소 끼리 삽입 정렬을 수행한다. 
			gap /= 3; //gap 값은 홀,짝 형태로 줄어든다.
		}
	}
};

void Shell(int* arr, int n){ //Shell Sort
	ShellSorter shs;
	steady_clock::time_point start, end; nanoseconds result; 
	start = steady_clock::now();

	shs.ShellSort(arr, n);

	end = steady_clock::now(); result = end - start;
	cout<<"3. Shell Sort                  : "<<result.count()<<"ns"<<endl; //알고리즘 실행시간
}