셸 정렬

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

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

1. 개요

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

2. 알고리즘

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

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

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

	₁	₂	₃	₄	₅	₆	₇	₈	₉	₁₀	₁₁	₁₂
입력 데이터	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. 동작 방식

셸 정렬은 삽입 정렬을 최적화한 알고리즘이다. 삽입 정렬의 경우, 각 요소는 한 번에 한 칸씩 이동한다. 하지만 셸 정렬은 멀리 떨어진 요소들을 먼저 교환하여 정렬 속도를 높인다.^[5]
동작 방식:1. 간격(h) 설정: 정렬할 리스트에서 일정 간격(h)을 정한다. 이 간격은 처음에는 크고 점차 줄어든다.

2. h-정렬: 각 간격(h)에 대해, h번째 요소들끼리 비교하여 정렬한다. 즉, 리스트를 h개의 부분 리스트로 나누어 각 부분 리스트를 삽입 정렬로 정렬한다. 이를 'h-정렬'이라고 한다.^[5]

3. 간격 감소 및 반복: 간격(h)을 줄여가면서 h-정렬을 반복한다. 간격이 1이 될 때까지, 즉 리스트 전체가 하나의 부분 리스트가 될 때까지 반복한다.^[5]

4. 최종 정렬: 간격이 1이 되면, 사실상 일반적인 삽입 정렬을 수행하는 것과 같다. 하지만 이전 단계에서 이미 대부분 정렬이 이루어졌기 때문에 훨씬 빠르게 완료된다.^[6]
예시: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]
간격이 5, 3, 1인 경우의 셸 정렬 예시:

	₁	₂	₃	₄	₅	₆	₇	₈	₉	₁₀	₁₁	₁₂
입력 데이터	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의 거듭제곱으로 하는 예시:초기 데이터:

8

3

1

2

7

5

6

4

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로 설정한다. 같은 색으로 표시된 숫자들은 같은 그룹에 속하며, 각 그룹 내에서 삽입 정렬을 수행한다.

8

3

1

2

7

5

6

4

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

7

3

1

2

8

5

6

4

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

7

3

1

2

8

5

6

4

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

1

2

6

3

7

4

8

5

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

1

2

6

3

7

4

8

5

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

1

2

3

4

5

6

7

8

3. 간격 결정 방법

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

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

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

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

평균 비교 횟수와 관련하여 Ciura의 시퀀스^[15]가 가장 잘 알려진 성능을 가지고 있으며, 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은 배열의 크기) 어떤 간격 수열이 최적인지는 아직 미해결 문제로 남아있다.^[39]

일반항 (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^[3]
$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^[7]
$2^k - 1$	$1, 3, 7, 15, 31, 63, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	히바드, 1963^[8]
$2^k + 1$ , 1로 시작	$1, 3, 5, 9, 17, 33, 65, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	Papernov & Stasevich, 1965^[9]
$2^p 3^q$ 형태의 연속 숫자(3-smooth 숫자)	$1, 2, 3, 4, 6, 8, 9, 12, \ldots$	$\Theta\left(N \log^2 N\right)$	프랫, 1971^[1]
$\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,^[10] 프랫, 1971에 기반^[1]
$\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,^[11] 커누스^[10]
$4^k + 3 \cdot 2^{k-1} + 1$ , 1로 시작	$1, 8, 23, 77, 281, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1982^[5]
$\begin{cases}$	$1, 5, 19, 41, 109, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1986^[12]
$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^[13]
$\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^[14]
알 수 없음 (실험적으로 파생됨)	$1, 4, 10, 23, 57, 132, 301, 701$		Ciura, 2001^[15]
$\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^[16]
$\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^[17]

수열의 일반항 (k ≥ 1)	실제 수열	최악 계산 시간	비고
$\left\lfloor\frac{n}{2^k}\right\rfloor$	$\left\lfloor\frac{n}{2}\right\rfloor,$	$\Omicron(n^2)$	도널드 셸이 처음 고안한 수열.^[36]
$\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^[37] 프랫, 1971^[40]에 기반함. 평균 계산 시간은 $\Omicron(n^{1.25})$ 이다.^[37]^[38]
$4^k + 3 \cdot 2^{k-1} + 1$	$1, 8, 23, 77, 281, \ldots$	$\Omicron\left(n^\frac{4}{3}\right)$	세지윅, 1982^[41]
$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^[40] 알려진 수열 중 최악 계산 시간이 최소가 되는 수열. 간격을 좁히는 방법이 너무 세밀하여 실용성은 낮다.^[39]

이러한 수열을 정렬 간격으로 이용할 때는 (요소 수 이내에서) 큰 숫자부터 좁혀나간다. $\frac{3^k - 1}{2}$ 를 사용하는 경우, 간격 h를 121→40→13→4→1로 한다(h를 3으로 정수 나누기 하면 된다).

4. 시간 복잡도

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

셸의 원래 간격 수열( $\left\lfloor\frac{N}{2^k}\right\rfloor$ )을 사용하는 경우, 입력 배열의 이진 표현에 연속적인 0이 많이 포함되어 있으면 최악의 경우 Θ(''N''²) 비교를 수행한다.^[3] 예를 들어, 중앙값보다 크고 작은 요소가 각각 홀수 및 짝수 위치를 차지하는 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^[3]
$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^[7]
$2^k - 1$	$1, 3, 7, 15, 31, 63, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	히바드, 1963^[8]
$2^k + 1$ , 1로 시작	$1, 3, 5, 9, 17, 33, 65, \ldots$	$\Theta\left(N^\frac{3}{2}\right)$	Papernov & Stasevich, 1965^[9]
$2^p 3^q$ 형태의 연속 숫자(3-smooth 숫자)	$1, 2, 3, 4, 6, 8, 9, 12, \ldots$	$\Theta\left(N \log^2 N\right)$	프랫, 1971^[1]
$\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,^[10] 프랫, 1971에 기반^[1]
$\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,^[11] 커누스^[10]
$4^k + 3 \cdot 2^{k-1} + 1$ , 1로 시작	$1, 8, 23, 77, 281, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1982^[5]
$\begin{cases}$	$1, 5, 19, 41, 109, \ldots$	$O\left(N^\frac{4}{3}\right)$	세지윅, 1986^[12]
$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^[13]
$\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^[14]
알 수 없음 (실험적으로 파생됨)	$1, 4, 10, 23, 57, 132, 301, 701$		Ciura, 2001^[15]
$\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^[16]
$\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^[17]

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

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

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

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

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

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

만큼 빠르게 증가한다는 것을 보였다.^[29]^[30]

5. 안정성

셸 정렬은 삽입 정렬을 최적화한 형태로, 멀리 떨어진 요소들을 교환하여 정렬하는 방식이다. 셸 정렬은 동일한 값을 가진 요소의 상대적인 순서를 보장하지 않는 불안정한 정렬이다.^[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 코드이다.^[1]

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)의 간격 수열을 사용하여 내부 삽입 정렬을 수행한다.^[1]

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. 활용

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

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

참조

_[1] 서적 Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) https://apps.dtic.mi[...] Garland 2021-09-07
_[2] 웹사이트 Shellsort & Comparisons http://www.cs.wcupa.[...] 2015-11-14
_[3] 논문 A High-Speed Sorting Procedure http://penguin.ewu.e[...] 2011-10-18
_[4] 웹사이트 Shell sort https://xlinux.nist.[...] National Institute of Standards and Technology 2007-07-17
_[5] 서적 Algorithms in C https://archive.org/[...] Addison-Wesley
_[6] 서적 The C Programming Language Prentice Hall
_[7] 논문 A High-Speed Sorting Procedure
_[8] 논문 An Empirical Study of Minimal Storage Sorting
_[9] 논문 A Method of Information Sorting in Computer Memories http://www.mathnet.r[...]
_[10] 서적 The Art of Computer Programming. Volume 3: Sorting and Searching Addison-Wesley
_[11] 논문 Improved Upper Bounds on Shellsort https://hal.inria.fr[...]
_[12] 논문 A New Upper Bound for Shellsort
_[13] 서적 Handbook of Algorithms and Data Structures: In Pascal and C Addison-Wesley
_[14] 서적 Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture North-Holland Publishing Co.
_[15] 서적 Proceedings of the 13th International Symposium on Fundamentals of Computation Theory Springer-Verlag
_[16] arXiv Empirically Improved Tokuda Gap Sequence in Shellsort 2021-12-21
_[17] arXiv Optimization Perspectives on Shellsort 2023-01-01
_[18] 서적 Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching Addison-Wesley
_[19] 웹사이트 How to choose the lengths of my sub sequences for a shell sort? https://stackoverflo[...] 2018-05-22
_[20] arXiv Optimal Gap Sequences in Shellsort for {{math|''n'' ≤ 16}} Elements 2021-12-21
_[21] 논문 A Phenomenon in the Theory of Sorting https://core.ac.uk/d[...] 1972-04
_[22] 논문 On Shellsort and the Frobenius Problem https://bora.uib.no/[...] 1989-03
_[23] 논문 A good case for Shellsort 1989
_[24] 논문 Analysis of a Shellsort Algorithm 1973-12
_[25] 논문 An Analysis of (''h'', ''k'', 1)-Shellsort http://pdfs.semantic[...] 2019-03-04
_[26] 논문 Shellsort with Three Increments http://www2.math.uu.[...]
_[27] 논문 A Lower Bound on the Average-Case Complexity of Shellsort https://homepages.cw[...] 2000-09
_[28] 논문 On the average-case complexity of Shellsort https://homepages.cw[...] 2018-03
_[29] 서적 Proceedings., 33rd Annual Symposium on Foundations of Computer Science 1992-10-24
_[30] 논문 Lower Bounds for Shellsort http://engineering.n[...] 1997-05
_[31] 논문 A Lower Bound on the Size of Shellsort Sorting Networks 1993
_[32] 웹사이트 libc/stdlib/stdlib.c http://git.uclibc.or[...] 2014-10-29
_[33] 웹사이트 kernel/groups.c https://github.com/t[...] 2012-05-05
_[34] 웹사이트 bzip2/blocksort.c https://www.ncbi.nlm[...] 2011-03-30
_[35] 웹사이트 Shellsort & Comparisons http://www.cs.wcupa.[...] 2016-03-20
_[36] 논문 A High-Speed Sorting Procedure http://penguin.ewu.e[...]
_[37] 서적 The Art of Computer Programming. Volume 3: Sorting and Searching Addison-Wesley
_[38] 서적 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造マイナビ
_[39] 웹사이트 Analysis of Shellsort and Related Algorithms https://www.cs.princ[...] 1996
_[40] 서적 Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) http://www.dtic.mil/[...] Garland
_[41] 서적 Algorithms in C https://archive.org/[...] Addison-Wesley
_[42] 서적 Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) http://www.dtic.mil/[...] Garland
_[43] 웹인용 Shellsort & Comparisons http://www.cs.wcupa.[...] 2019-11-20

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com