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

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

리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다.

앞선 글에서 삽입 정렬 에 대해 설명하였다. 삽입 정렬의 경우, 기존 배열이 어느정도 정렬되어있냐에 따라 수행 시간이 크게 차이난다. 현재 선택한 원소의 적절한 삽입 위치가 멀다면, 비교 & 이동해야하는 횟수가 많아지면서 수행 시간이 늘어나는 것이다. 정렬된 상태와 가까운 배열일수록 수행 시간은 단축된다. 

 

즉, 삽입 정렬은 초기 리스트가 정렬이 된 상태일 경우 더 효율적이다.

→ 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다.

→ 쉘 정렬은 삽입 정렬을 보완한 방법!

 

쉘 정렬의 시간 복잡도는 아직까지도 정확하게는 알려진 바가 없으나, 삽입 정렬의 시간 복잡도인 O(n²) 보다 빠르다. 대략적으로 O(n^1.25) 정도로 알려져 있다. 

---

2. 쉘 정렬의 수행 방식

쉘 정렬 과정

① 초기 시작 간격(gap)을 정한다. (간격을 k라고 하자.)

② k개씩 그룹으로 묶어 리스트를 나눈다. 

③ 각 그룹의 n번째 원소들끼리 삽입 정렬을 수행한다. (1 ≤ n ≤ k)

④ k의 크기를 반으로 줄인다.

⑤ k가 1이 될 때까지 다시 ②부터 반복한다.

 

여기서 초기 gap인 k를 얼마로 설정해야 하느냐는 정해져있지 않으므로 자유롭게 설정해도 무방하다. 하지만 간격을 얼마로 설정하냐에 따라 쉘 정렬이 수행되는 속도가 달라진다. 현재까지 알려진 가장 좋은 수행 속도를 보이는 간격은 [1, 4, 10, 23, 57, 132, 301, 701, 1750 ...] 이다. 

 

 

<쉘 정렬 예시>

gap의 초기값을 4로 설정하여 쉘 정렬을 수행한 예시이다.

---

 

 

---

3. 쉘 정렬 구현 (C++)

#include <iostream>
using namespace std;

//쉘 정렬 함수(여기서 n은 배열의 크기)
void shell_sort(int arr[], int n) {

	int i, j, temp;
	int gap = n / 2;	//gap크기 설정 (원하는 값으로 설정 가능)	
	while (gap > 0) {

		//gap으로 나눈 후 각 부분 리스트 삽입 정렬 수행
		for (i = gap; i < n; i++) {
			temp = arr[i];
			j = i;
			while (j >= gap && arr[j - gap] > temp) {
				arr[j] = arr[j - gap];
				j -= gap;
			}
			arr[j] = temp;
		}

		gap /= 2;	//gap의 크기를 반으로 줄인 후 다시 반복 (gap이 1이 될 때까지)
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int list[] = { 20,10,90,50,60,80,40,30,0,70 };

	cout << "정렬 전" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}

	shell_sort(list, 10);

	cout << "\n\n정렬 후" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}
}

실행 결과 정상적으로 쉘 정렬이 수행된 것을 확인할 수 있다.