EXAMPLE을 사용한 쉘 정렬 알고리즘
사라 첸
쉘 정렬이란?
Shell의 방법 또는 데이터 구조의 Shell 정렬은 효율적인 내부 비교 정렬 알고리즘입니다. 1959년 도널드 셸(Donald Shell)이 초기 아이디어를 제안했을 때 이름을 따서 명명되었습니다. 셸 정렬은 삽입 정렬 알고리즘의 일반화된 확장입니다.
이 정렬 알고리즘의 기본 아이디어는 멀리 떨어져 있는 요소를 그룹화하고 그에 따라 정렬하는 것입니다. 그런 다음 점차적으로 그 사이의 간격을 줄입니다. 셸 정렬은 멀리 떨어져 있는 요소를 비교하고 교환하여 삽입 정렬의 평균 케이스 시간 복잡도를 극복합니다.
간격으로 알려진 이 간격은 일부 최적의 간격 시퀀스에 따라 감소됩니다. 쉘 정렬의 실행 시간도 이러한 순서에 따라 달라집니다. Shell의 원래 시퀀스, Knuth의 공식, Hibbard의 증분 등과 같은 여러 갭 시퀀스가 있습니다. Shell의 원래 갭 시퀀스는 다음과 같습니다. n/2, n/4, n/8, ……….1
쉘 정렬 알고리즘
쉘 정렬 알고리즘의 단계 또는 절차는 다음과 같습니다.
단계 1) 간격 값 h = n/2를 초기화합니다. (이 예에서 n은 배열의 크기입니다.)
단계 2) 간격 h의 거리 내에 있는 모든 요소를 하위 목록에 넣습니다.
단계 3) 삽입 정렬을 사용하여 해당 하위 목록을 정렬합니다.
단계 4) 새로운 간격, h=h/2를 설정합니다.
단계 5) h>0이면 2단계로 이동합니다. 그렇지 않으면 6단계로 이동합니다.
단계 6) 결과 출력은 정렬된 배열이 됩니다.
쉘 정렬 작동 방식
삽입 정렬에서는 요소가 한 번에 한 위치씩만 이동됩니다. 이와 반대로 쉘 정렬은 간격 값을 기준으로 배열을 더 작은 조각으로 나누고 해당 조각에 대해 삽입 정렬을 실행합니다.
점차적으로 간격 값은 감소하고 분할된 조각의 크기는 증가합니다. 조각은 미리 개별적으로 정렬되므로 해당 조각을 병합하는 데 필요한 단계는 다음과 같습니다. 삽입 정렬.
다음 GIF는 쉘 정렬의 데모를 보여줍니다. 이 데모에서 빨간색과 파란색으로 표시된 값은 삽입 정렬을 기반으로 비교되고 교환됩니다. 그런 다음 간격이 감소하고 쉘 정렬은 거의 정렬된 데이터에서 삽입 정렬을 시작합니다.
Shell Sort 알고리즘의 작동
쉘 정렬 알고리즘의 다음 예를 살펴보겠습니다. 이 예에서 쉘 정렬을 사용하여 다음 배열을 정렬합니다.
단계 1) 여기서 배열 크기는 8입니다. 따라서 간격 값은 h = 8/2 또는 4가 됩니다.
단계 2) 이제 모든 요소를 4 거리에 저장합니다. 우리의 경우 하위 목록은 {8, 1}, {6, 4}, {7, 5}, {2, 3}입니다.
단계 3) 이제, 해당 하위 목록은 삽입 정렬을 사용하여 정렬됩니다. 삽입 정렬에서는 임시 변수를 사용하여 두 숫자를 비교한 다음 그에 따라 정렬합니다.
배열은 작업을 교환한 후 다음과 같습니다.
단계 4) 이제 구간의 초기값을 줄여보겠습니다. 새로운 간격은 h=h/2 또는 4/2 또는 2가 됩니다.
단계 5) 2>0이므로 2단계로 이동하여 2의 거리에 있는 모든 요소를 저장합니다. 이 경우 하위 목록은 다음과 같습니다.
{1, 5, 8, 7}, {4, 2, 6, 3}
그런 다음 이러한 하위 목록은 삽입 정렬을 사용하여 정렬됩니다. 첫 번째 하위 목록을 비교하고 교환한 후 배열은 다음과 같습니다.
두 번째 하위 목록을 정렬한 후 원래 배열은 다음과 같습니다.
그러면 다시 간격이 줄어듭니다. 이제 간격은 h=h/2 또는 2/1 또는 1이 됩니다. 따라서 삽입 정렬 알고리즘을 사용하여 수정된 배열을 정렬합니다.
삽입 정렬의 단계별 절차 설명은 다음과 같습니다.
간격은 다시 2로 나누어집니다. 이때 간격은 0이 됩니다. 따라서 6단계로 이동합니다.
단계 6) 간격이 0이므로 이 시간을 기준으로 배열이 정렬됩니다. 정렬된 배열은 다음과 같습니다.
의사 코드
Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
for (i = interval; i & lt; n; i += 1)
temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
a[j] = a[j - interval];
a[j] = temp;
End
C/의 쉘 정렬 프로그램C++
입력:
//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
for (int interval = size / 2; interval > 0; interval /= 2) {
for (int i = interval; i < size; i += 1) {
int temp = data[i];
int j;
for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
data[j] = data[j - interval];
}
data[j] = temp;
}
}
}
int main() {
int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
int size = sizeof(data) / sizeof(data[0]);
ShellSort(data, size);
cout << "Sorted Output: \n";
for (int i = 0; i < size; i++)
cout << data[i] << " ";
cout << "\n";
}
출력:
Sorted Output: 1 2 3 4 5 6 7 8
쉘 정렬 예 Python
입력:
#Shell Sort Example in Python
def ShellSort(data, size):
interval = size // 2
while interval > 0:
for i in range(interval, size):
temp = data[i]
j = i
while j >= interval and data[j - interval] > temp:
data[j] = data[j - interval]
j -= interval
data[j] = temp
interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)
출력:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
쉘 정렬의 응용
Shell Sort의 중요한 응용 프로그램은 다음과 같습니다.
- 쉘 정렬은 다음에서 사용됩니다. 리눅스 커널 호출 스택을 사용하지 않기 때문입니다.
- uClibc 라이브러리는 Shell 정렬을 사용합니다.
- bzip2 압축기는 쉘 정렬을 사용하여 재귀 초과를 중지합니다.
쉘 정렬의 장점과 단점
| 장점 | 단점 |
|---|---|
| 스택 호출이 필요하지 않습니다. | 대규모 배열 크기에는 효율적이지 않습니다. |
| 쉬운 구현. | 널리 분산된 요소에는 비효율적입니다. |
| 간격이 덜 넓은 요소에 효율적입니다. |
쉘 정렬 복잡도 분석
Shell Sort의 시간 복잡도
쉘 정렬 알고리즘의 시간 복잡도는 O(n^2)입니다. 추론은 다음과 같습니다.
가장 좋은 시나리오의 경우, 배열이 이전에 정렬되었을 때 모든 간격에 대한 테스트의 총량은 log n과 같습니다. 따라서 복잡도는 O(n*log n)이 됩니다.
최악의 시나리오의 경우 배열이 요소에 가장 많은 수의 비교가 필요한 방식으로 구성되어 있다고 가정해 보겠습니다. 그러면 마지막 반복까지 모든 요소가 비교 및 전환되지 않습니다. 따라서 최종 증분에 필요한 전체 비교는 O(n^2)입니다.
결론적으로 시간 복잡도는 다음과 같습니다.
- 가장 복잡한 경우: O(n*log n)
- 평균 케이스 복잡도: O(n*log n)
- 최악의 경우 복잡도: O(n^2)
쉘 정렬의 실행 시간 복잡도는 사용된 갭 증가 시퀀스에 크게 의존합니다. 그러나 쉘 정렬에 가장 적합한 증가 시퀀스는 아직 알려지지 않았습니다.
쉘 정렬 공간 복잡도
이 비교 정렬에서는 추가 보조 공간이 필요하지 않습니다. 따라서 이러한 종류의 알고리즘의 공간 복잡도는 O(1)입니다.
