셸 정렬(Shell Sort)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① 셸 정렬(shell sort)는 삽입 정렬의 일반화된 형태이며, 먼 거리에 있는 요소들 간의 교환을 가능하게 해서 성능을 높였다.

  ㉠ 셸 정렬은 셸의 방법(shell 's method)으로도 불린다.

② 셸 정렬의 최악의 시간 복잡도는 삽입 정렬과 마찬가지로 O(log(n))이다.

  ㉠ 그렇지만, 퀵 정렬 다음으로 셸 정렬이 두 번째로 빠르다.

③ 셸 정렬의 기본 원리는 다음과 같다.

  ㉠ 정수로 된 갭 시퀀스를 정한다. (h1>h2>h3>h4>...hk = 1)

    ⓐ 갭은 하위 배열 간의 간격을 의미하며, 최종적으론 하위 정렬 간의 간격이 1이 되어야 함을 의미한다.

 

상대적으로 구현하기 쉬운 것은 2번이다.

    ⓑ 갭이 1씩 줄어드는 갭 시퀀스를 가진 셸 정렬이 삽입 정렬이다.

 

삽입 정렬(Insertion Sort)과 이진 삽입 정렬(Binary Insertion Sort)

  ㉡ 현재 갭으로 하위 배열을 분할하고, 하위 배열을 삽입 정렬로 정렬한다.

 

  ㉢  최종적으로는 갭의 크기가 1이 될 떄까지 ㉡을 수행한다.

④ 셸 정렬의 의사 코드(psuedo code)는 다음과 같다.

 

	function shellSort(array)
	n = length(array)
	gap = n / 2
	while gap > 0 do
	for i = gap to n - 1 do
	temp = array[i]
	j = i
	while j >= gap and array[j - gap] > temp do
	array[j] = array[j - gap]
	j = j - gap
	end while
	array[j] = temp
	end for
	gap = gap / 2
	end while
	return array
	end function

view raw psuedocode.txt hosted with ❤ by GitHub

⑤ 셸 정렬의 구현 코드는 다음과 같다.

 

	#include<iostream>
	#include<vector>
	#include<chrono>
	using namespace std;
	using namespace chrono;
	vector<int>randomVector(int n) {
	vector<int> vec(n);
	srand(time(NULL));
	for (int i = 0; i < n; i++) {
	vec[i] = rand() % 100;
	}
	return vec;
	}
	vector<int> shell_sort(int n) {
	vector<int>vec = randomVector(n);
	auto tik = chrono::system_clock::now();
	int gap = n / 2;
	while (gap > 0) {
	for (int i = gap; i < n; i++) {
	int temp = vec[i];
	int j = i;
	while (j >= gap && vec[j - gap] > temp) {
	vec[j] = vec[j - gap];
	j -= gap;
	}
	vec[j] = temp;
	}
	gap /= 2;
	}
	auto tok = chrono::system_clock::now();
	cout << endl;
	cout << n << ":" << chrono::duration_cast<microseconds>(tok - tik).count() << "ms \n";
	return vec;
	}
	int main() {
	shell_sort(10);
	shell_sort(100);
	shell_sort(1000);
	shell_sort(10000);
	return 0;
	}

view raw example.cpp hosted with ❤ by GitHub

	10:0ms
	100:0ms
	1000:0ms
	10000:1487ms

view raw terminal hosted with ❤ by GitHub

⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮
㉠㉡㉢㉣㉤㉥㉦㉧㉨㉩㉪㉫㉬㉭
ⓐⓑⓒⓓⓔⓕⓖⓗⓘⓙⓚⓛⓜ