Shell Sort

기본 아이디어

Insertion Sort를 기반으로 한다.
서로 멀리 떨어져 있는 숫자들을 Insertion Sort하기 시작하여 점점 두 숫자들 사이의 거리(gap)을 좁혀서 정렬한다.
최종적으로 gap=1 이 되면 , 원래의 insertion sort를 실행하는 것과 동일해진다.
gap >1 단계에서 거북이 데이터를 목표 위치 근처로 많이 이동했기에 gap=1 단계에서는 정렬된 상태에 많이 가까운 상태이다.

같은 gap을 가지는 모든 gap sequence에 Insertion Sort를 실행한다.

구현

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
void swap(int& i, int& j) {
	int k;
	k = i;
	i = j;
	j = k;
}

void ShellSort(vector<int>& A) {
	int n = A.size();
	int shrinkRatio = 2;
	int gap = A.size() / shrinkRatio;
	int tmp;
	int j;
	while (gap > 0) {
		for (int i = 0; i < n; i++) {
			tmp = A[i];
			for (j = i; (j >= gap) && (A[j - gap] > tmp); j -= gap) {
				A[j] = A[j - gap];
			}
			A[j] = tmp;
		}
		gap /= shrinkRatio;
	}
}

void print(vector<int> A) {
	for (auto el : A) {
		cout << el << " ";
	}
	cout << endl;
}
void main() {
	vector<int> A = { 9,6,3,1,2,4,5,7,8 };
	print(A);
	ShellSort(A);
	print(A);
}

실행 과정

1. 간격 설정 : 일반적으로 리스트 크기의 절반을 초기 간격으로 사용한다.
2. 부분 리스트 정렬 : 지정된 gap에 따라 부분 리스트를 형성하고 각 부분 리스트에 대해 Insertion Sort를 진행한다.
3. 간격 감소 : 간격을 줄이고 2단계로 돌아간다. 일반적으로 간격을 절반으로 줄인다.
4. 전체 리스트 정렬 : 간격이 1이 될 때 전체 리스트에 대해 삽입 정렬을 수행한다.