셸 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

셸 정렬은 삽입 정렬을 개선한 정렬 알고리즘으로, 멀리 떨어진 요소들을 교환하여 정렬 속도를 향상시킨다. 임의의 간격(h)을 두고 h-정렬된 상태를 만들며, 간격을 줄여가며 최종적으로는 h=1이 되어 전체 배열을 정렬한다. 셸 정렬의 성능은 간격 결정 방법에 따라 달라지며, 다양한 간격 수열이 제안되었지만, 아직 최적의 간격 수열은 밝혀지지 않았다. 시간 복잡도는 간격 수열에 따라 다르며, 최악의 경우 O(n^2)에서 O(n log^2 n)까지 다양하다. 셸 정렬은 퀵 정렬보다 구현이 간단하고 호출 스택을 사용하지 않아 임베디드 시스템이나 qsort 함수 구현에 활용되며, 내성 정렬의 하위 알고리즘으로도 사용된다.

셸 정렬

📚 더 읽어볼만한 페이지

정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
비교 정렬 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
비교 정렬 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.

1. 개요
2. 알고리즘
- 2.1. 동작 방식
- 2.2. 예제
3. 간격 결정 방법
- 3.1. 주요 간격 수열
4. 시간 복잡도
5. 안정성
6. 소스 코드
- 6.1. [[파이썬]]
- 6.2. [[C++]]
7. 활용

2. 알고리즘

셸 정렬은 삽입 정렬을 개선한 알고리즘으로, 삽입 정렬이 인접한 요소끼리만 비교, 교환하는 것과 달리 '간격(gap)'을 두고 멀리 떨어진 요소들을 비교, 교환한다. 이 간격을 점차 줄여나가면서 정렬을 반복 수행한다.

간단히 설명하면, 1024개의 숫자가 있을 때 첫 간격(h)을 512로 설정하고, 첫 번째 절반의 각 요소를 두 번째 절반의 요소와 비교한다. 두 번째 간격(k)은 256으로 배열을 4개의 섹션(0, 256, 512, 768)으로 나누고 각 섹션의 첫 번째 항목이 서로 상대적으로 정렬되어 있는지 확인한 다음, 각 섹션의 두 번째 항목 등을 확인하는 방식이다. 간격은 다양하게 설정할 수 있지만, 마지막 간격은 항상 1로 하여 정렬을 완료한다.

간격이 5, 3, 1인 셸 정렬의 예시는 다음과 같다.

👆

좌우로 밀어서 보기

	1>\| ₂ \|\| ₃ \|\| ₄	5>\| ₆ \|\| ₇ \|\| ₈	9>\| ₁₀ \|\| ₁₁ \|\| ₁₂
입력 데이터	62	83	18	53	07	17	95	86	47	69	25	28
5-정렬 후	17	28	18	47	07	25	83	86	53	69	62	95
3-정렬 후	17	07	18	47	28	25	69	62	53	83	86	95
1-정렬 후	07	17	18	25	28	47	53	62	69	83	86	95

5-정렬은 5개의 하위 배열에 삽입 정렬을 수행하고, 3-정렬은 3개의 하위 배열, 1-정렬은 전체 배열에 대해 삽입 정렬을 수행한다.

셸 정렬은 안정적인 정렬이 아니며, 입력이 부분적으로 정렬될 때 더 빠르게 실행되는 적응형 정렬 알고리즘이다.

```c
# 배열 a[0...n-1]을 정렬한다.
gaps = [701, 301, 132, 57, 23, 10, 4, 1] # 치우라 간격 수열

# 가장 큰 간격에서 시작하여 간격이 1이 될 때까지 줄여나간다.
# 삽입 정렬과 유사하지만 각 단계에서 1 대신 간격을 사용한다.
foreach (gap in gaps)
{
# 간격 정렬을 모든 간격의 요소에 대해 수행한다.
# 각 루프는 a[0..gap-1]을 간격 정렬된 순서로 둔다.
for (i = gap; i < n; i += 1)
{
# a[i]를 temp에 저장하고 i 위치에 구멍을 만든다.
temp = a[i]
# a[i]의 올바른 위치를 찾을 때까지 이전의 간격 정렬된 요소를 위로 이동시킨다.
for (j = i; (j >= gap) && (a[j - gap] > temp); j -= gap)
{
a[j] = a[j - gap]
}
# temp (원래 a[i])를 올바른 위치에 넣는다.
a[j] = temp
}
}

2.1. 동작 방식

셸 정렬은 삽입 정렬을 최적화한 알고리즘이다. 삽입 정렬의 경우, 각 요소는 한 번에 한 칸씩 이동한다. 하지만 셸 정렬은 멀리 떨어진 요소들을 먼저 교환하여 정렬 속도를 높인다.

동작 방식:

1. 간격(h) 설정: 정렬할 리스트에서 일정 간격(h)을 정한다. 이 간격은 처음에는 크고 점차 줄어든다.
2. h-정렬: 각 간격(h)에 대해, h번째 요소들끼리 비교하여 정렬한다. 즉, 리스트를 h개의 부분 리스트로 나누어 각 부분 리스트를 삽입 정렬로 정렬한다. 이를 'h-정렬'이라고 한다.
3. 간격 감소 및 반복: 간격(h)을 줄여가면서 h-정렬을 반복한다. 간격이 1이 될 때까지, 즉 리스트 전체가 하나의 부분 리스트가 될 때까지 반복한다.
4. 최종 정렬: 간격이 1이 되면, 사실상 일반적인 삽입 정렬을 수행하는 것과 같다. 하지만 이전 단계에서 이미 대부분 정렬이 이루어졌기 때문에 훨씬 빠르게 완료된다.

예시:

1024개의 숫자로 구성된 배열을 셸 정렬로 정렬하는 과정을 생각해보자.

* 첫 번째 간격 (h=512): 배열을 두 개의 부분 배열(0, 512), (1, 513), ... , (511, 1023)로 나눈다. 각 부분 배열의 요소들을 비교하여 정렬한다.
* 두 번째 간격 (h=256): 배열을 네 개의 부분 배열(0, 256, 512, 768), (1, 257, 513, 769), ... , (255, 511, 767, 1023)로 나눈다. 각 부분 배열의 요소들을 비교하여 정렬한다.
* 마지막 간격 (h=1): 배열 전체를 하나의 부분 배열로 보고 삽입 정렬을 수행한다.

간격(h) 값은 다양하게 설정할 수 있지만, 마지막 간격은 반드시 1이어야 한다.

간격이 5, 3, 1인 경우의 셸 정렬 예시:

👆

좌우로 밀어서 보기

	1>\| ₂ \|\| ₃ \|\| ₄	5>\| ₆ \|\| ₇ \|\| ₈	9>\| ₁₀ \|\| ₁₁ \|\| ₁₂
입력 데이터	62	83	18	53	07	17	95	86	47	69	25	28
5-정렬 후	17	28	18	47	07	25	83	86	53	69	62	95
3-정렬 후	17	07	18	47	28	25	69	62	53	83	86	95
1-정렬 후	07	17	18	25	28	47	53	62	69	83	86	95

* 5-정렬: 5개의 부분 배열에 대해 삽입 정렬을 수행한다.
* 3-정렬: 3개의 부분 배열에 대해 삽입 정렬을 수행한다.
* 1-정렬: 전체 배열에 대해 삽입 정렬을 수행한다.

셸 정렬은 갭(간격)을 이용한 삽입 정렬을 수행하기 때문에, 동일한 요소의 순서가 바뀔 수 있어 안정적인 정렬은 아니다. 하지만 입력 데이터가 부분적으로 정렬되어 있을 때 더 빠르게 동작하는 적응형 정렬 알고리즘이다.

간격을 2의 거듭제곱으로 하는 예시:

초기 데이터:

👆

좌우로 밀어서 보기

1. h=4: 같은 색으로 표시된 그룹끼리 삽입 정렬을 수행한다.

👆

좌우로 밀어서 보기

2. h=2: 같은 색으로 표시된 그룹끼리 삽입 정렬을 수행한다.

👆

좌우로 밀어서 보기

3. h=1: 전체 데이터를 하나의 그룹으로 보고 삽입 정렬을 수행한다.

👆

좌우로 밀어서 보기

최종 정렬 결과:

👆

좌우로 밀어서 보기

2.2. 예제

주어진 배열 [8, 3, 1, 2, 7, 5, 6, 4]를 셸 정렬로 정렬하는 과정을 단계별로 살펴보자. 이 예에서는 간격(h)을 4 → 2 → 1로 감소시킨다.

1. h = 4

처음에는 간격을 4로 설정한다. 같은 색으로 표시된 숫자들은 같은 그룹에 속하며, 각 그룹 내에서 삽입 정렬을 수행한다.

👆

좌우로 밀어서 보기

위 표를 삽입 정렬하면 다음과 같다.

👆

좌우로 밀어서 보기

2. h = 2

다음으로, 간격을 2로 줄인다. 이전 단계에서 정렬된 그룹들을 다시 더 작은 그룹으로 나누어 삽입 정렬을 수행한다.

👆

좌우로 밀어서 보기

위 표를 삽입 정렬하면 다음과 같다.

👆

좌우로 밀어서 보기

3. h = 1

마지막으로, 간격을 1로 설정한다. 이는 전체 배열이 하나의 그룹이 됨을 의미하며, 이 그룹에 대해 삽입 정렬을 수행하여 최종 정렬된 배열을 얻는다.

👆

좌우로 밀어서 보기

삽입 정렬을 수행하면 다음과 같다.

👆

좌우로 밀어서 보기

3. 간격 결정 방법

셸 정렬의 성능은 간격(h)을 어떻게 결정하느냐에 따라 크게 달라진다. 셸 정렬에서 사용되는 간격은 처음에는 큰 값으로 시작하여 점차 감소하는데, 큰 간격을 사용하면 요소들이 원래 위치에서 멀리 이동할 수 있어 배열 내의 무질서를 빠르게 줄일 수 있다.

간격이 너무 크면 오버헤드가 발생하고, 너무 작으면 각 패스의 속도가 느려진다. 따라서 적절한 간격 수열을 선택하는 것이 중요하다. 1을 포함하는 모든 간격 수열은 결국 배열을 정렬하지만, 사용되는 수열에 따라 셸 정렬의 속성은 크게 달라질 수 있다.

초기 간격을 배열 크기의 절반으로 하고, 각 단계마다 간격을 절반으로 줄이는 방법을 생각해 볼 수 있다. 그러나 이 방법은 최악의 경우 Θ(N²) 비교를 수행하게 된다. 더 효율적인 정렬을 위해 다양한 간격 수열이 제안되었다.

고넷과 바에자-예이츠는 연속적인 갭의 비율이 대략 2.2와 같을 때 평균적으로 가장 적은 비교를 수행한다는 것을 관찰했다. 세지윅은 낮은 최대 공약수를 갖거나 쌍별로 상호 소수인 갭을 사용하는 것을 권장한다.

평균 비교 횟수와 관련하여 Ciura의 시퀀스가 가장 잘 알려진 성능을 가지고 있으며, 701보다 큰 갭은 재귀 공식 $h_k = \lfloor 2.25 h_{k-1} \rfloor$ 에 따라 확장할 수 있다. 실용적인 적용을 위해서는 토쿠다의 시퀀스 $h_k = \lceil h'_k \rceil$ ( $h'_k = 2.25 h'_{k-1} + 1$ , $h'_1 = 1$ )가 권장될 수 있다.

3.1. 주요 간격 수열

다음은 셸 정렬에서 사용되는 주요 간격 수열과 그 특징을 나타내는 표이다. (n은 배열의 크기) 어떤 간격 수열이 최적인지는 아직 미해결 문제로 남아있다.

👆

좌우로 밀어서 보기

일반항 (k ≥ 1)	구체적인 갭	최악의 경우 시간 복잡도	저자 및 발표 연도
$\left\lfloor\frac{N}{2^k}\right\rfloor$	$1, 2, \ldots, \left\lfloor\frac{N}{4}\right\rfloor,$	$\Theta\left(N^2\right)$ [예: N = 2^p일 때]	도널드 셸, 1959
$2 \left\lfloor\frac{N}{2^{k+1}}\right\rfloor + 1$	$1, 3, \ldots, \; 2 \left\lfloor\frac{N}{8}\right\rfloor + 1,$	$\Theta\left(N^\frac{3}{2}\right)$	Frank & Lazarus, 1960
$2^k - 1$	$1, 3, 7, 15, 31, 63, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	히바드, 1963
$2^k + 1$ , 1로 시작	$1, 3, 5, 9, 17, 33, 65, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	Papernov & Stasevich, 1965
$2^p 3^q$ 형태의 연속 숫자(3-smooth 숫자)	$1, 2, 3, 4, 6, 8, 9, 12, \ldots$	$\Theta\left(N \log^2 N\right)$	프랫, 1971
$\frac{3^k - 1}{2}$ , $\left\lceil\frac{N}{3}\right\rceil$ 보다 크지 않음	$1, 4, 13, 40, 121, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	커누스, 1973, 프랫, 1971에 기반
$\begin{align}$	$1, 3, 7, 21, 48, 112, \ldots$	$O\left(N^{1 + \sqrt{\frac{8\ln\left(5/2\right)}{\ln(N)}}}\right)$	Incerpi & 세지윅, 1985, 커누스
$4^k + 3 \cdot 2^{k-1} + 1$ , 1로 시작	$1, 8, 23, 77, 281, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1982
$\begin{cases}$	$1, 5, 19, 41, 109, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1986
$h_k = \max\left\{\left\lfloor \frac{5h_{k-1}-1}{11} \right\rfloor, 1\right\}, h_0 = N$	$1, \ldots, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N-1}{11} \right\rfloor-\frac{1}{11}\right\rfloor,$		고넷 & 바에자-예이츠, 1991
$\left\lceil \frac{1}{5} \left(9\cdot \left(\frac{9}{4}\right)^{k-1} - 4 \right) \right\rceil$ (또는 동등하게, $\left\lceil \frac{\left(9/4\right)^k-1}{\left(9/4\right)-1} \right\rceil$ )	$1, 4, 9, 20, 46, 103, \ldots$		Tokuda, 1992
알 수 없음 (실험적으로 파생됨)	$1, 4, 10, 23, 57, 132, 301, 701$		Ciura, 2001
$\left\lceil \frac{\gamma^k-1}{\gamma-1} \right\rceil, \gamma = 2.243609061420001\ldots$	$1, 4, 9, 20, 45, 102, 230, 516, \ldots$		Lee, 2021
$\left\lfloor 4.0816\cdot 8.5714^{\frac{k}{2.2449}} \right\rfloor$	$1, 4, 10, 27, 72, 187, 488, \ldots$		Skean, Ehrenborg, Jaromczyk, 2023

👆

좌우로 밀어서 보기

수열의 일반항 (k ≥ 1)	실제 수열	최악 계산 시간	비고
$\left\lfloor\frac{n}{2^k}\right\rfloor$	$\left\lfloor\frac{n}{2}\right\rfloor,$	$\Omicron(n^2)$	도널드 셸이 처음 고안한 수열.
$\frac{3^k - 1}{2}$ 　( $\left\lceil\frac{n}{3}\right\rceil$ 이하)	$1, 4, 13, 40, 121, \ldots$	$\Omicron\left(n^\frac{3}{2}\right)$	도널드 커누스, 1973 프랫, 1971에 기반함. 평균 계산 시간은 $\Omicron(n^{1.25})$ 이다.
$4^k + 3 \cdot 2^{k-1} + 1$	$1, 8, 23, 77, 281, \ldots$	$\Omicron\left(n^\frac{4}{3}\right)$	세지윅, 1982
$2^p 3^q$ ( $p \ge 0 ,q \ge 0$ )	$1, 2, 3, 4, 6, 8, 9, 12, \ldots$	$\Omicron\left(n \log^2 n\right)$	프랫, 1971 알려진 수열 중 최악 계산 시간이 최소가 되는 수열. 간격을 좁히는 방법이 너무 세밀하여 실용성은 낮다.

이러한 수열을 정렬 간격으로 이용할 때는 (요소 수 이내에서) 큰 숫자부터 좁혀나간다.

\frac{3^k - 1}{2}

를 사용하는 경우, 간격 h를 121→40→13→4→1로 한다(h를 3으로 정수 나누기 하면 된다).

4. 시간 복잡도

셸 정렬의 시간 복잡도는 사용하는 간격 수열에 따라 달라진다. 최악의 경우 시간 복잡도는 $O(n^2)$ 에서 $O(n \log^2 n)$ 까지 다양하다. 평균 시간 복잡도에 대한 분석은 복잡하며, 특정 간격 수열에 대해서는 아직 정확하게 밝혀지지 않았다.

셸의 원래 간격 수열( $\left\lfloor\frac{N}{2^k}\right\rfloor$ )을 사용하는 경우, 입력 배열의 이진 표현에 연속적인 0이 많이 포함되어 있으면 최악의 경우 Θ(N²) 비교를 수행한다. 예를 들어, 중앙값보다 크고 작은 요소가 각각 홀수 및 짝수 위치를 차지하는 2의 거듭제곱 크기의 배열에서 이러한 경우가 발생한다.

다음은 지금까지 발표된 대부분의 제안된 간격 수열과 그에 따른 최악의 경우 시간 복잡도를 나타낸 표이다.

👆

좌우로 밀어서 보기

일반항 (k ≥ 1)	구체적인 갭	최악의 경우 시간 복잡도	저자 및 발표 연도
$\left\lfloor\frac{N}{2^k}\right\rfloor$	$1, 2, \ldots, \left\lfloor\frac{N}{4}\right\rfloor,$	$\Theta\left(N^2\right)$	셸, 1959
$2 \left\lfloor\frac{N}{2^{k+1}}\right\rfloor + 1$	$1, 3, \ldots, \; 2 \left\lfloor\frac{N}{8}\right\rfloor + 1,$	$\Theta\left(N^\frac{3}{2}\right)$	Frank & Lazarus, 1960
$2^k - 1$	$1, 3, 7, 15, 31, 63, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	히바드, 1963
$2^k + 1$ , 1로 시작	$1, 3, 5, 9, 17, 33, 65, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	Papernov & Stasevich, 1965
$2^p 3^q$ 형태의 연속 숫자(3-smooth 숫자)	$1, 2, 3, 4, 6, 8, 9, 12, \ldots$	$\Theta\left(N \log^2 N\right)$	프랫, 1971
$\frac{3^k - 1}{2}$ , $\left\lceil\frac{N}{3}\right\rceil$ 보다 크지 않음	$1, 4, 13, 40, 121, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	커누스, 1973, 프랫, 1971에 기반
$\begin{align}$	$1, 3, 7, 21, 48, 112, \ldots$	$O\left(N^{1 + \sqrt{\frac{8\ln\left(5/2\right)}{\ln(N)}}}\right)$	Incerpi & 세지윅, 1985, 커누스
$4^k + 3 \cdot 2^{k-1} + 1$ , 1로 시작	$1, 8, 23, 77, 281, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1982
$\begin{cases}$	$1, 5, 19, 41, 109, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1986
$h_k = \max\left\{\left\lfloor \frac{5h_{k-1}-1}{11} \right\rfloor, 1\right\}, h_0 = N$	$1, \ldots, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N-1}{11} \right\rfloor-\frac{1}{11}\right\rfloor,$		고넷 & 바에자-예이츠, 1991
$\left\lceil \frac{1}{5} \left(9\cdot \left(\frac{9}{4}\right)^{k-1} - 4 \right) \right\rceil$	$1, 4, 9, 20, 46, 103, \ldots$		Tokuda, 1992
알 수 없음 (실험적으로 파생됨)	$1, 4, 10, 23, 57, 132, 301, 701$		Ciura, 2001
$\left\lceil \frac{\gamma^k-1}{\gamma-1} \right\rceil, \gamma = 2.243609061420001\ldots$	$1, 4, 9, 20, 45, 102, 230, 516, \ldots$		Lee, 2021
$\left\lfloor 4.0816\cdot 8.5714^{\frac{k}{2.2449}} \right\rfloor$	$1, 4, 10, 27, 72, 187, 488, \ldots$		Skean, Ehrenborg, Jaromczyk, 2023

평균 비교 횟수와 관련하여 Ciura의 시퀀스가 가장 잘 알려진 성능을 가지고 있다.

콜모고로프 복잡성 이론을 적용하면, 셸 정렬에서 평균 연산 횟수/실행 시간의 하한은 다음과 같다.

* p ≤ log₂N일 때 Ω(pN^1+1/p)
* p > log₂N일 때 Ω(pN)

따라서 셸 정렬은 배열 크기의 로그에 비례하여 간격의 수가 증가하는 간격 수열을 사용할 때만 평균 시간이 점근적으로 N logN처럼 증가할 가능성이 있다. 그러나 셸 정렬이 비교 정렬에 최적인 이 점근적 평균 시간 복잡도를 달성할 수 있는지는 알려져 있지 않다.

셸 정렬의 모든 버전의 최악의 경우 복잡도는 더 높은 차수를 가진다. 플랙스턴, 푸넨 및 쉘은

\Omega\left(N \left( {\log N \over \log \log N} \right)^2\right)

만큼 빠르게 증가한다는 것을 보였다.

5. 안정성

셸 정렬은 삽입 정렬을 최적화한 형태로, 멀리 떨어진 요소들을 교환하여 정렬하는 방식이다. 셸 정렬은 동일한 값을 가진 요소의 상대적인 순서를 보장하지 않는 불안정한 정렬이다. 갭(gap)을 이용한 삽입 과정에서 동일한 요소들이 서로 위치를 바꾸면서 원래의 순서를 잃게 되기 때문이다.

6. 소스 코드

c
/* 배열 a[0...n-1]을 정렬한다. */
int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1}; // 치우라 간격 수열
int n = sizeof(gaps) / sizeof(gaps[0]);

for (int g = 0; g < n; g++)
{
int gap = gaps[g];
for (int i = gap; i < n; i++)
{
int temp = a[i];
int j = i;
for (; j >= gap && a[j - gap] > temp; j -= gap)
{
a[j] = a[j - gap];
}
a[j] = temp;
}
}
```

마르친 치우라(Marcin Ciura)의 간격 수열을 사용하는 삽입 정렬 기반의 C 코드이다.

6.1. [[파이썬]]

python
def Shellsort(arr):

h = 1
while h < len(arr):
h = 3*h + 1
h = h//3

while h > 0:
for i in range(h,len(arr)):
k=i-h
key=arr[i]
while k>=0 and key < arr[k]:
arr[k+h] = arr[k]
k=k-h
arr[k+h] = key
h = h//3
return arr
```
마르친 치우라(Marcin Ciura)의 간격 수열을 사용하여 내부 삽입 정렬을 수행한다.

6.2. [[C++]]

cpp
template
void 셸_정렬(RandomAccessIterator first, RandomAccessIterator last, Compare comp,
const double sk = 3.14159265358979323846264338327950, const short m = 5)
{
if(first == last)
return;
double gap = distance(first, last);
std::ptrdiff_t h;

do
{
gap /= sk;
h = (std::ptrdiff_t)(gap + 0.5);
if(h < m)
h = 1;
RandomAccessIterator H = first + h;
for(RandomAccessIterator i = H; i < last; ++i)
{
if(comp(*i, *(i - h)))
{
auto t = std::move(*i);
RandomAccessIterator j = i;
do
{
*j = std::move(*(j - h));
j -= h;
}while(H <= j && comp(t, *(j - h)));
*j = std::move(t);
}
}
}while(1 < h);
}
```
마르친 치우라(Marcin Ciura)의 간격 수열을 기반으로 하는 셸 정렬의 C++ 구현이다. 이 코드는 템플릿을 사용하여 다양한 데이터 타입과 비교 함수에 적용할 수 있도록 설계되었다.

7. 활용

셸 정렬은 임베디드 시스템과 같이 제한된 환경에서 사용될 수 있다. C 표준 라이브러리의 일부 구현에서는 퀵 정렬보다 코드가 적고 호출 스택을 사용하지 않는 셸 정렬을 대신 사용하기도 한다. 과거에는 리눅스 커널에서도 셸 정렬이 사용되었다.

셸 정렬은 내성 정렬의 하위 알고리즘으로도 사용될 수 있는데, 이는 짧은 하위 배열을 정렬하고 재귀 깊이가 지정된 한도를 초과할 때 속도 저하를 방지하는 데 사용된다.