셸 정렬 알고리즘 (예제 포함)

셸 정렬이란 무엇인가요?

셸 정렬(Shell Sort), 또는 셸 방법(Shell's method)이라고도 불리는 이 알고리즘은 효율적인 제자리 비교 기반 정렬 알고리즘입니다. 1959년에 이 아이디어를 제시한 도널드 셸의 이름을 따서 명명되었으며, 분산된 데이터에서 삽입 정렬이 보이는 제곱 항등식 문제를 극복한 일반화된 확장 알고리즘입니다.

기본적인 아이디어는 서로 멀리 떨어져 있는 요소들을 그룹화하고, 각 그룹을 삽입 정렬을 사용하여 정렬한 다음, 간격을 단계적으로 줄여 1이 될 때까지 정렬하는 것입니다. 이렇게 하면 배열이 거의 정렬된 상태가 됩니다.

이 간격, 즉 음정은 Shell의 원본, Knuth의 원본, Hibbard의 원본 또는 Sedgewick의 원본과 같은 선택된 순서를 따릅니다. Shell의 원본은 다음과 같습니다. n/2, n/4, ..., 1.

쉘 정렬 알고리즘

단계 1) 간격 값 h를 n/2로 초기화합니다. 여기서 n은 배열의 크기입니다.

단계 2) 거리 h만큼 떨어진 모든 요소를 ​​하위 목록에 넣습니다.

단계 3) 삽입 정렬을 사용하여 각 하위 목록을 정렬합니다.

단계 4) 새로운 간격 h = h/2로 설정합니다.

단계 5) h > 0이면 2단계로 돌아갑니다. 그렇지 않으면 6단계로 이동합니다.

단계 6) 이제 생성된 배열은 완전히 정렬되었습니다.

쉘 정렬 작동 방식

삽입 정렬에서는 요소가 한 번에 한 위치씩만 이동합니다. 반면 셸 정렬은 간격을 기준으로 배열을 간격이 넓은 하위 목록으로 나누고 각 하위 목록에 대해 삽입 정렬을 수행합니다.

간격이 줄어들수록 하위 목록의 크기는 커집니다. 이전 단계에서 데���터가 부분적으로 정렬된 상태로 남아 있기 때문에 간격이 작을수록 전체 경로를 실행하는 것보다 훨씬 적은 스왑 횟수가 필요합니다. 삽입 정렬 처음부터. 아래 그림은 셸 정렬 과정의 한 단계를 보여줍니다.

셸 정렬 알고리즘의 작동 원리 및 예시

아래 배열을 셸 정렬을 사용하여 정렬해 보겠습니다.

단계 1) 배열의 크기는 8이므로 초기 간격 값은 h = 8/2 = 4입니다.

단계 2) 네 위치 간격으로 그룹 요소를 만듭니다. 하위 목록: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

단계 3) 삽입 정렬을 사용하여 각 하위 목록을 정렬합니다. 요소가 이동하는 동안 임시 변수에 배치되는 값을 저장합니다. 교환 후 배열은 다음과 같습니다.

단계 4) 간격을 줄입니다. 새로운 간격은 h = 4/2 = 2입니다.

단계 5) 2 > 0이므로 2단계로 돌아가서 두 위치 간격으로 요소를 그룹화합니다: {1, 5, 8, 7} 및 {4, 2, 6, 3}.

첫 번째 하위 목록을 정렬합니다. 그러면 배열은 다음과 같이 됩니다.

두 번째 하위 목록을 정렬한 후:

간격을 다시 h = 2/2 = 1로 줄입니다. 간격이 1이 되면 Shell Sort는 아래와 같이 전체 배열에 대해 최종 삽입 정렬을 수행합니다.

단계 6) 구간을 다시 나누면 0이 됩니다. 이제 배열이 완전히 정렬되었습니다.

가짜-Code 셸 정렬용

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > 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]

쉘 정렬의 응용

셸 정렬은 스택 공간이나 단순성이 중요한 현대 시스템에서 여전히 사용됩니다.

• The 리눅스 커널 호출 스택을 피하는 것이 중요한 곳에서 Shell Sort를 사용합니다.
• uClibc 내장 C 라이브러리는 메모리 사용량을 낮게 유지하기 위해 Shell Sort를 사용합니다.
• bzip2는 블록 정렬 중 깊은 재귀 호출을 방지하기 위해 셸 정렬(Shell Sort)을 사용합니다.
• 내장 펌웨어는 재귀 호출이 제한되는 소규모 데이터 세트에 대해 셸 정렬을 선호합니다.

쉘 분류의 장점과 단점

쉘 정렬 복잡도 분석

Shell Sort의 시간 복잡도

셸 정렬의 시간 복잡도는 사용된 간격 순서에 따라 달라집니다.

최상의 경우, 배열이 이미 거의 정렬된 상태라면 각 단계에서 필요한 테스트 횟수는 로그 함수적인 수에 불과하므로 시간 복잡도는 O(n log n)입니다.

최악의 경우, 배열은 요소들이 최대 비교 횟수를 필요로 하도록 구성되어 있으며, Shell의 원래 시퀀스를 사용하면 마지막 증가 연산이 O(n^2)의 시간 복잡도로 지배적인 역할을 합니다.

1. 최고의 복잡도: O(n log n)
2. 평균적인 경우의 시간 복잡도는 간격 순서에 따라 O(n log n)에서 O(n^(4/3))까지입니다.
3. 최악의 경우 복잡도: Shell의 원래 시퀀스를 사용할 때 O(n^2)

최적의 ���용 갭 시퀀스는 여전히 연구 과제이지만, Sedgewick 및 Ciura 시퀀스는 실제 사용에서 우수한 성능을 보입니다.

쉘 정렬 공간 복잡도

셸 정렬은 보조 배열을 필요로 하지 않으므로 입력 크기에 관계없이 공간 복잡도가 O(1)입니다. 이는 셸 정렬의 가장 강력한 실질적인 장점 중 하나입니다.

자주 묻는 질문