[Java] 셸 정렬(Shell Sort)

서정범·2023년 3월 13일

Sort algorithm

자료구조와 알고리즘

목록 보기

14/30

셸 정렬

셸 정렬이란?

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

삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하는 것이 문제였습니다. 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨리 떨어진 곳이라면 많은 이동을 해야만 했습니다.

그래서, 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않습니다.

셸 정렬 알고리즘에 있어서 중요한 개념인 증분값에 대해서 좀 더 알아보고 넘어가도록 하겠습니다.

증분값

증분값을 어떻게 결정하느냐에 따라서 셸 정렬 알고리즘의 효율성이 바뀌기 때문에 증분값(h값)을 결정하는 것은 매우 중요합니다.

먼저 아래 그림을 통해서 어떤 방식으로 동작하는지 확인 후 증분값을 설명하도록 하겠습니다.

증분값은 위의 그림에서 4, 2, 1칸 만큼 나눈 값을 증분값이라고 합니다.(gap이라고도 부릅니다.)

증분값이 중요한 이유는 다음과 같다.

위와 같이 8개의 요소가 있는데, 거기서 4, 2, 1로 증분값을 결정해서 비교를 했다.

증분값이 4일때 0, 4 / 1, 5 / 2, 6 / 3, 7 요소들을 비교했다.
증분값이 2일때 0, 2, 4, 6/ 1, 3, 5, 7 요소들을 비교했다.

두 과정에서 비교 요소가 겹져지고 말았다. 이것이 단순히 8개의 요소가 아닌 굉장히 많은 요소가 있고 그런 와중에 이러한 불필요한 비교 연산이 들어가면 시간적으로 낭비가 심할 것이다.

그래서 증분값(h값)의 경우 서로 배수가 되지 않도록 해야 합니다. 이렇게 하면 요소가 충분히 섞여 효율적인 정렬을 기대할 수 있습니다.

동작 과정

증분값 결정
증분값이 1로 될 때까지 반복문을 진행
1. for: int i = h로 해서 앞의 요소와 비교하면서 n - 1요소 까지 비교, 교환
2. 이후 증분값을 감소 시키고 a과정을 반복한다.

기본적인 동작 방식은 삽입 정렬과 유사하기 때문에 증분값을 결정하는 것에서만 신경을 써주면 그렇게 어렵지 않은 코드입니다.

코드

void shellSort(int[] a, int n) {
  int h;
  // 최대한 그룹 섞기 위한 증분값(h값) 결정
  for( h = 1; h < n / 9; h = h * 3 + 1);

  for( ; h > 0; h /= 3) {
    for(int i = h; i < n; i++) {
      int j;
      int tmp = a[i];
      for(j = i - h; j >= 0 && a[j] > tmp; j -= h)
        a[j + h] = a[j];
      // for문의 경우 조건식에 맞았을 경우 for문 안의 코드를 실행 후 증감식을 실행 후 다시 조건문을 확인한다.
      // 따라서, 아래와 같이 코드를 해줘야 바뀌는 것임.
      a[j + h] = tmp;
    }
}
/* 
for( ; h >= 1; h /= 3) {
  for(int i = h; i < n; i++) {
    int j;
    int temp = a[i];
    for(j = i; j - h >= 0 && a[j - h] > temp; j -= h)
      a[j] = a[j - h];
    a[j] = temp;
  }
}
*/