셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘 입니다.

→ 단순 삽입 정렬 방식에서 여러개의 그룹으로 쪼개어 정렬

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

// 셸 정렬 함수
void shell_sort(int* arr, int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i]; // 현재 삽입할 값
            int j;

            // gap 간격으로 왼쪽으로 이동하며 정렬
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp; // temp를 올바른 위치에 삽입
        }
    }
}