자료구조 - 쉘 정렬

[쉘 정렬(Shell Sort)]

쉘 정렬(Shell Sort)은 삽입 정렬의 개선된 버전으로, 간격을 두고 요소들을 비교하고 정렬하여 전체 리스트를 점진적으로 정렬하는 방법입니다.

간격은 점점 줄어들며, 마지막 단계에서는 간격이 1이 되어 삽입 정렬과 동일하게 동작합니다.

쉘 정렬은 일반적으로 삽입 정렬보다 빠릅니다.

 

 

 

쉘 정렬 과정

1. 초기 간격을 설정합니다. 일반적으로 리스트 길이의 절반으로 시작합니다.
2. 간격이 줄어들 때마다 리스트의 요소를 비교하여 삽입 정렬과 유사하게 정렬합니다.
3. 간격을 줄여나가면서 이 과정을 반복합니다.
4. 마지막 간격이 1이 될 때 전체 리스트가 정렬됩니다

 

쉘 정렬 의사 코드

함수 shellSort(arr):
    n = 배열의 길이(arr)
    gap = n // 2  // 초기 간격 설정

    while gap > 0:
        for i = gap부터 n까지:
            temp = arr[i]
            j = i

            while j >= gap 그리고 arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = temp

        gap //= 2  // 간격을 절반으로 줄임

    반환 arr

 

쉘 정렬 예제

예시 리스트: [64, 25, 12, 22, 11]

첫 번째 간격(gap = 2):
    (64, 12) 비교하여 교환 → [12, 25, 64, 22, 11]
    (25, 22) 비교 → 교환하지 않음
    (64, 11) 비교하여 교환 → [12, 25, 11, 22, 64]

두 번째 간격(gap = 1):
    (12, 25) 비교 → 교환하지 않음
    (25, 11) 비교하여 교환 → [12, 11, 25, 22, 64]
    (25, 22) 비교하여 교환 → [12, 11, 22, 25, 64]
    (25, 64) 비교 → 교환하지 않음
    (11, 12) 비교하여 교환 → [11, 12, 22, 25, 64]

 

쉘 정렬 코드

#include <iostream>
#include <vector>

using namespace std;

// 쉘 정렬 함수
void shellSort(vector<int>& arr) 
{
    int n = arr.size();  // 배열의 길이

    // 초기 간격 설정
    for (int gap = n / 2; gap > 0; gap /= 2) 
    {
        // 간격(gap)을 두고 삽입 정렬 수행
        for (int i = gap; i < n; i++)
        {
            int temp = arr[i];
            int j = i;

            // 간격(gap) 만큼 떨어진 요소들끼리 비교 및 교환
            while (j >= gap && arr[j - gap] > temp) 
            {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

int main()
{
    vector<int> arr = {64, 25, 12, 22, 11};  // 예제 리스트

    cout << "정렬 전: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    shellSort(arr);  // 쉘 정렬 수행

    cout << "정렬 후: ";
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

 

ㅇㅅㅇ