[정렬] 셸 정렬(Shell Sort) 알고리즘

-삽입 정렬을 간단하게 변형

(삽입정렬은 이웃한 위치로만 이동하기때문에 삽입되어야할 위치가 현재위치랑 많이 떨어져있으면 많은 이동을 해야한다는 문제점이 있음)

-멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴 

-배열을 일정한 간격으로 나누어 부분적으로 삽입 정렬을 수행한 후, 간격을 줄여가며 전체적으로 삽입정렬을 수행하는 방식으로 동작 한다

-간격을 줄여가는 과정에서 마지막으로 간격이 1인 삽입정렬을 수행하면 정렬이 완료 

-정렬해야할 리스트의 k번째 요소를 추출해서 부분리스트를 만든다 이 때 k를 gap이라고 한다 

-gap은 홀수로 하는 게 좋다, 짝수라면 +1을 한다

-gap이 1이 될 때까지 반복 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;

int main() {

    int n;
    scanf("%d", &n);
    int a[1000] = { 0, };

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    //gap을 줄여나가고 1이 되면 정렬이 완료된다
    for (int gap = n / 2; gap > 0; gap /= 2) {
        if ((gap % 2) == 0) {
            gap++;
        }

        //삽입 정렬
        for (int i = gap; i < n; i += 1) {
            int temp = a[i];//temp는 정렬할 숫자
            int j;
            //정렬할 숫자보다 배열에 있는 원소가 더 크면 
            for (j = i; j >= gap && a[j - gap] > temp; j -= gap) {
                a[j] = a[j - gap]; //temp의 자리에 더 큰 배열의 원소의 값이 들어간다 
            }
            a[j] = temp; //정렬할 숫자를 앞에 넣어준다 
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d\n", a[i]);
    }
    

  
    return 0;
}

가장 바깥 for문은 gap을 줄여나가는 것이고 1이 될때까지 반복하는 반복문이다

 

두번째 for문부터는 삽입정렬을 수행하는 코드이다

삽입정렬과 동일하게 정렬할 숫자를 temp에 넣고

 

 

세번째 for문을 돌면서 앞에 있는 원소들과 비교하면서 삽입할 위치를 찾는다

 

이 부분에서는 현재 삽입할 원소 temp와 그 앞의 원소들을 비교하여, temp보다 큰 원소가 발견되는 경우 그 원소를 한 칸 뒤로 이동시키는 작업을 수행한다. 이때, 이동시키는 거리는 gap이다 

temp보다 작은 원소가 발견된거나 배열의시작점 (j-gap)에 도달할 때까지 j를 gap씩 감소시키면서 배열의 앞쪽으로 이동한다 

 

이 때 인덱스 j는 간격 gap만큼 뒤로 이동하면서 비교를 수행한다

삽입할 위치를 찾으면 해당 위치에 temp을 삽입한다