Shell sort

  1 #include <stdio.h>
  2
  3 void shellsort(int * arr, int arrNum);
  4
  5 int main(void)
  6 {
  7     int arr[10] = {31, 7, 3, 2, 18, 73, 19, 1, 8, 10};
  8
  9     shellsort(arr, 10);
 10
 11     return 0;
 12 }
 13
 14 void shellsort(int * arr, int arrNum)
 15 {
 16     int i, j, gap = arrNum;
 17     int temp;
 18
 19     while(gap > 1)
 20     {
 21         gap = gap / 2;
 22
 23         for(i = gap; i < arrNum; i++)
 24         {
 25             temp = arr[i];
 26             j = i - gap;
 27
 28             while((temp<arr[j]) && (j>=0))
 29             {
 30                 arr[j + gap] = arr[j];
 31                 j = j - gap;
 32             }
 33             arr[j + gap] = temp;
 34         }
 35     }
 36
 37     for(i = 0; i < arrNum; i++)
 38     {
 39         printf("%d ", arr[i]);
 40     }
 41 }

-----

 16     int i, j, gap = arrNum;
 17     int temp;
 18
 19     while(gap > 1)
 20     {
 21         gap = gap / 2;

이 부분을

 16     int i, j, gap = 1;
 17     int temp;
 18   
 19     while(gap < arrNum) gap = 3 * gap + 1;
 20     while(gap > 1)
 21     {
 22         gap = gap / 3;

찾아보니 이런 식으로도 표현한다.
하지만 이 부분이 완전히 이해가 가지 않는다.