개념

셸 정렬

셸 정렬은 다음과 같은 과정으로 나눈다.

1. 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.
2. 데이터를 다시 잘게 나누어서 삽입 정렬한다.
3. 이렇게 계속 하여 마침내 정렬이 된다.

$h = h\times 3 + 1$ 을 사용했을 때 가장 효율적이라고 한다.

Python

import random

n = 20
a = [random.randrange(0, 40) for _ in range(n)]
print(" < origin >")
print(*a)

# Shell  Sort
h = 1
while h < n:
    h = 3 * h + 1
h = h//3

while h > 0:
    for i in range(h, n):
        j = i - h
        v = a[i]
        while j >= 0 and a[j] > v:
            a[j+h] = a[j]
            j -= h
        a[j+h] = v
    h = h//3

print("\\n< Shell Sort >")
print(*a)

C - Generalization

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define BASE(base, idx) (char*)base + (idx)*width

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

void shell_sort(
    void* base, int nelem, int width,
    int (*fcmp)(const void*, const void*)) {
    int i, h = 1;
    while (h < nelem)
        h = h * 3 + 1;
    h /= 3;

    while (h > 0) {
        for (i = h; i < nelem; i++) {
            void* v = malloc(width);
            memcpy(v, BASE(base, i), width);
            int j = i - h;
            while (j >= 0 && fcmp(BASE(base, j), v) > 0) {
                memcpy(BASE(base, j + h), BASE(base, j), width);
                j -= h;
            }
            memcpy(BASE(base, j + h), v, width);
        }
        h /= 3;
    }
}

int main() {
    srand((unsigned int)time(NULL));

    int i, n = 20;
    int* a = (int*)calloc(n, sizeof(int));
    for (i = 0; i < n; i++)
        a[i] = rand() % 50;

    printf("origin : \\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);

    shell_sort(a, n, sizeof(int), cmp);

    printf("\\n\\nshell sorted : \\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

C++

#include <ctime>
#include <iostream>
#include <random>

using namespace std;

template <typename T>
void shell_sort(T* a, int n) {
    **int h = 1;
    while (h < n)
        h = 3 * h + 1;
    h /= 3;

    while (h > 0) {
        for (int i = h; i < n; i++) {
            int j = i - h;
            T v = a[i];
            while (j >= 0 && a[j] > v) {
                a[j + h] = a[j];
                j -= h;
            }
            a[j + h] = v;
        }
        h /= 3;
    }**
}

int main() {
    mt19937 mt((unsigned int)time(nullptr));
    uniform_int_distribution<int> gen(0, 49);

    int n = 20;
    int* a = new int[20];
    for (int i = 0; i < n; i++) {
        a[i] = gen(mt);
    }

    cout << "origin : \\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    shell_sort(a, n);

    cout << "\\n\\nshell sort : \\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
}

back_to_top