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

버블정렬이나 삽입정렬은 이웃하는 원소의 자리바꿈이다
하지만 쉘 정렬은 그룹화를 시켜 정렬하는 방식으로, 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 이동시키고 앞부분의 큰 숫자는 뒷부분으로 이동시킨다

예를 들어 

숫자가 이렇게 있다고 하자 
이 배열을 간격 5로 그룹화를 하면

이렇게 그룹이 지어진다, 그럼 여기서 이제 그룹1 안에서 삽입정렬, 그룹2 안에서 삽입정렬을 해주면된다

그룹별 정렬을 하고 나면

이렇게 정렬이 되고, 5의 갭차이로 그룹을 나누었으니 다음에는 3의 갭차이로 그룹을 나누어 정렬한다
그리고 마지막에는 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
5. while (j >= h) and (A[j-h] > CurrentElement)
6. A[j] = A[j-h]
7. j = j-h
8. A[j] = CurrentElement
9. return A

갭차이 만큼의 앞에 있는 숫자가 뒤 숫자보다 크면 둘의 자리를 바꿔준다
그리고 currentElement는 앞에 있는 숫자가 되는 것이다

---

코드로 구현하면

#include <iostream>

#define N 15
using namespace std;

void shellSort(int A[]) {
	int currentElemnet=0;

	cout << "Before Sort : ";

	for (int i = 0; i < N; i++) {
		cout << A[i]<<" ";
	}

	cout << "\n" << "<<<<<<<Shell Sorting>>>>>>>>>" << "\n";
	for (int h = 5; h >= 1; h-=2) {
		for (int i = h; i <= N - 1; i++) {
			currentElemnet = A[i];

			int j = i;
			
			while (j >= h && A[j - h] > currentElemnet) {
				A[j] = A[j - h];
				j -= h;
			}
			A[j] = currentElemnet;
		}
		cout << "Gap " << h<<" >> ";
		for (int j = 0; j < N; j++) {
			cout << A[j]<<" ";
		}
		cout << "\n";
	}
}

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

위에서 설계한 알고리즘을 그대로 구현해주면 된다

---

시간복잡도

시간복잡도는 사용하는 간격에 따라 분석해야하기 때문에 아직 풀리지 않은 문제이다