처음하시는 분들을 위한 C언어 기초강의 시즌2 - 44 [정렬 알고리즘(셀 정렬, Shell sort)]

제 44강) 정렬 알고리즘 - 셀 정렬

오늘은 정렬 알고리즘의 마지막 시간으로 "셀 정렬(Shell sort)"에 대해서 알아봅니다.

셀 정렬은 삽입 알고리즘을 보완한 알고리즘입니다.

 

 

셀 정렬이란

(사진 출처 : 위키백과 - 셸 정렬)

셀 정렬은 "Donald Shell(도널드 셀)"이 고안해낸 알고리즘으로 삽입 정렬을 보완한 알고리즘입니다.

먼저 데이터를 여러 분류로 나누어 삽입정렬을 진행합니다.

요런식으로 일정 구간을 정하여 각각의 분류(그룹)를 만들어서 해당 분류 내에서 정렬을 시킵니다.

위에서 3개의 분류로 나뉜 값들을 각각 분류를 기준으로 정렬을 시켰습니다.

이렇게 정렬된 배열을 더 낮은 개수의 분류로 나눕니다.

이제 한 번 더 분류를 기준으로 정렬을 시킵니다.

이 정도까지 하면 대략 가장 큰 수들이 맨 뒤쪽으로 옮겨집니다.

이제 더 이상 분류하지 않고 바로 삽입정렬을 시킵니다.

이렇게 정렬이 완료됩니다.

 

보통 셀 정렬에서 분류를 정할 때에는 데이터의 개수를 N이라고 칭한다면 N/2를 많이 사용하지만 N/3 + 1이 가장 빠르다고 합니다.

(출처 : 위키백과 - 셸 정렬)

 

일반적으로 셀 정렬은 시간 복잡도가 들쑥 날쑥합니다.

그래서 최상일 경우에는 O(nlogn)이 나오며 최악일 경우에는 O(n^2)이 나옵니다.

 

위의 영상은 셀 정렬을 시각적인 춤으로 표현한 좋은 영상입니다.

꼭 보세요.

셀 정렬 구현

이제 셀 정렬을 구현하여 봅시다.

셀 정렬을 하기 위해서는 크게 2가지를 생각하면 됩니다.

1) 분류 만들기

2) 분류에 따른 삽입 정렬

 

먼저 셀 정렬의 기본적인 구현(분류에 관한)하여봅시다.

// 셀 정렬
void shell_sort(int* arr, int length)
{
    int cate = length;
    
    // 분류의 값이 1이 되면 탈출
    // (분류의 값이 1일때 완전 정렬이 일어났으므로)
    while (cate != 1)
    {
        // cate / 2 보다 빠르다고 합니다.
        cate = cate / 3 + 1;
 
        // i는 각 분류의 첫번째 요소
        // cate가 3이라면
        // 0: 분류 1의 첫 요소
        // 1: 분류 2의 첫 요소
        // 2: 분류 3의 첫 요소
        for (int i = 0; i < cate; i++)
        {
            // 각 분류별로 삽입정렬을 실행
            for (int j = i; j < length; j += cate)
            {
                insert_sort(arr, length, j, cate);
            }
        }
    }
}

저의 경우에는 분류를 나타내는 변수를 cate 라고 지었습니다.

 

이제 분류에 따른 삽입 정렬을 구현하여봅시다.

// 삽입 정렬
void insert_sort(int* arr, int length, int idx, int cate)
{
    int curValue;                   // 현재 선택한 위치의 값
    int tmp;                        // 값 스왑을 위한 변수
    int downPoint = idx - cate;     // 값 비교를 위한 변수의 인덱스
 
    while (1)
    {
        curValue = arr[idx];
 
        // 현재 선택한 값이 비교대상의 값보다 작으면
        if (curValue < arr[downPoint])
        {
            // 뒤로 값을 밀어낸다.
            tmp = arr[downPoint];
            arr[downPoint] = arr[downPoint + cate];
            arr[downPoint + cate] = tmp;
 
            // 현재 값의 위치를 비교대상의 위치로 변경
            idx = downPoint;
        }
        // 비교대상의 위치는 항상 감소
        downPoint -= cate;
 
        // 비교 위치가 0보다 적으면 탈출
        if (downPoint < 0)
            break;
    }
}

이전에 보았던 삽입 정렬과 같습니다만, 모든 변수를 한 번에 정렬하는 것이 아닌 특정 위치의, 특정 값을 정렬하는 것이기 때문에 그에 맞게 변경합니다.

 

#include <stdio.h>
 
// 배열 출력
void printArr(int* arr, int length, char* str)
{
    printf("%s: ", str);
    for (int i = 0; i < length; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
// 삽입 정렬
void insert_sort(int* arr, int length, int idx, int cate)
{
    int curValue;                    // 현재 선택한 위치의 값
    int tmp;                         // 값 스왑을 위한 변수
    int downPoint = idx - cate;      // 값 비교를 위한 변수의 인덱스
 
    while (1)
    {
        curValue = arr[idx];
 
        // 현재 선택한 값이 비교대상의 값보다 작으면
        if (curValue < arr[downPoint])
        {
            // 뒤로 값을 밀어낸다.
            tmp = arr[downPoint];
            arr[downPoint] = arr[downPoint + cate];
            arr[downPoint + cate] = tmp;
 
            // 현재 값의 위치를 비교대상의 위치로 변경
            idx = downPoint;
        }
        // 비교대상의 위치는 항상 감소
        downPoint -= cate;
 
        // 비교 위치가 0보다 적으면 탈출
        if (downPoint < 0)
            break;
    }
}
 
// 셀 정렬
void shell_sort(int* arr, int length)
{
    int cate = length;
    
    // 분류의 값이 1이 되면 탈출
    // (분류의 값이 1일때 완전 정렬이 일어났으므로)
    while (cate != 1)
    {
        // cate / 2 보다 빠르다고 합니다.
        cate = cate / 3 + 1;
 
        // i는 각 분류의 첫번째 요소
        // cate가 3이라면
        // 0: 분류 1의 첫 요소
        // 1: 분류 2의 첫 요소
        // 2: 분류 3의 첫 요소
        for (int i = 0; i < cate; i++)
        {
            // 각 분류별로 삽입정렬을 실행
            for (int j = i + cate; j < length; j += cate)
            {
                insert_sort(arr, length, j, cate);
            }
        }
    }
}
 
int main(void)
{
    int arr[] = { 4,1,2,8,7,11,17,9,55,6,13,22 };
    int length = sizeof(arr) / sizeof(int);
 
    printArr(arr, length, "정렬 전 배열");
    shell_sort(arr, length);
    printArr(arr, length, "정렬 후 배열");
    return 0;
}

 

이렇게 정렬 알고리즘을 배워보았습니다.

이 정렬 알고리즘 들은 상당히 많이 쓰이는 것들도 있고 안쓰는 것들도 있지만 전부 알아두시는 것이 좋습니다.

(면접볼 때 유용합니다.)