[알고리즘] 쉘 정렬 (shell sort)

쉘 정렬

버블 정렬의 경우, 작은 숫자가 배열의 앞부분으로 매우 느리게 이동.

삽입 정렬의 경우, 배열의 마지막원소가 입력에서 가장 작은 숫자라면, 그 숫자가 배열의 맨 앞으로 이동해야하므로, 모든 다른 숫자들이 1칸씩 오른쪽으로 이동해야함.

쉘 정렬 = 그룹의 크기를 줄여가며, 삽입정렬을 각 그룹마다 진행

수도코드 및 시간복잡도

입력:크기가 n인 배열A
출력:정렬된 배열A
for each gap h = [h0 > h1 > ... hk = 1] //큰 gap부터 차례로
for i = h to n-1{
	currentElem = A[i];
	j = i;
	while(j >= h and (A[j-h] > currentElem)) {
		A[j] = A[j-h];
		j = j-h;
	}
	A[j] = currentElem;
	}
return 배열 A

히바드 간격 2^k - 1을 사용하면 쉘 정렬의 시간복잡도는 O(n^1.5) - 계산 방법이 힘들다고 함 알아만 두기.

삽입정렬과 동일

최선 : O(n)

최악 : O(n^2)

불안정정렬

교재 문제 39번)p.271

문제와 같이 h-순서를 정하면 비교되는 원소들끼리 반복된다. 이때 수행시간은 O(n^2). 쉘 정렬은  각 pass 마다 비교 안된 원소들이 비교되어야 좋은 성능을 낸다.

코드(c)

/*입력:크기가 n인 배열A
출력 : 정렬된 배열A
for each gap h = [h0 > h1 > ... hk = 1] //큰 gap부터 차례로
for i = h to n - 1{
	currentElem = A[i];
	j = i;
	while (j >= h and (A[j - h] > currentElem)) {
		A[j] = A[j - h];
		j = j - h;
	}
	A[j] = currentElem;
}
return 배열 A
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int N;

void shellsort(int m[], int gap[])
{
	int j;
	for (int i = 0; i < 3; i++) {
		for (int k = gap[i]; k < N; k++)
		{
			int currentElem = m[k];
			j = k;
			while ((j >= gap[i]) && (m[j - gap[i]] > currentElem))
			{
				m[j] = m[j - gap[i]];
				j = j - gap[i];
			}
			m[j] = currentElem;
		}
	}
}
int main() {
	//입력받기
	scanf("%d", &N);
	int* m = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		int k;
		scanf("%d", &k);
		m[i] = k;
	}
	
	int gap [] = {5,3,1};
	shellsort(m, gap);
	//결과출력
	for (int i = 0; i < N; i++)
		printf("%d ", m[i]);
	return 0;

}

BOJ

2751 (c++)

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

1차시도) 시간초과 오류가 난다...

//쉘 정렬
#include <iostream>
#include <vector>
using namespace std;

int n;
void shellsort(vector<int>& a)
{
	int	gap = n / 2;

	while (gap > 0)
	{
		int j;
		for (int k = gap; k < n; k++)
		{
			int currentelem = a[k];
			j = k;
			while ((j >= gap) && (a[j - gap] > currentelem))
			{
				a[j] = a[j - gap];
				j = j - gap;
			}
			a[j] = currentelem;
		}
		//gap 조정
		if (gap == 1)//gap가 1인 경우
			break;
		gap = (gap + 1) / 2;
		
	}

	
}
int main() {
	//입력
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	//gap설정은 n / 4 로 홀수면 그대로, 짝수면 1더하기

	shellsort(a);
	//출력
	for (int i = 0; i < n; i++)
		cout << a[i] << endl;

	return 0;
}

2차시도) 
찾아보니, CIN, COUT의 입출력이 느리다고하여

아래 코드를 추가하였다. 그랬더니 됐당!

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

//쉘 정렬
#include <iostream>
#include <vector>
using namespace std;

int n;
void shellsort(vector<int>& a)
{
	int	gap = n / 2;

	while (gap > 0)
	{
		int j;
		for (int k = gap; k < n; k++)
		{
			int currentelem = a[k];
			j = k;
			while ((j >= gap) && (a[j - gap] > currentelem))
			{
				a[j] = a[j - gap];
				j = j - gap;
			}
			a[j] = currentelem;
		}
		//gap 조정
		if (gap == 1)//gap가 1인 경우
			break;
		gap = (gap + 1) / 2;
		
	}

	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//입력
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin>>a[i];
	//gap설정은 n / 4 로 홀수면 그대로, 짝수면 1더하기

	shellsort(a);
	//출력
	for (int i = 0; i < n; i++) {
		cout<<a[i];
		cout<<"\n";
	}

	return 0;
}

시간초과... ㅎㅎ