shellSort 이해하기

 static void shellSort(int[] a, int n) {
        for (int h = n / 2; h > 0; h /= 2) {
            for (int i = h; i < n; i++) {
                int j;
                int tmp = a[i]; //비교할 값 선택: 집게로 뽑았다고 생각
                for (j = i - h; j >= 0 && a[j] > tmp; j -= h) { //j가 0보다 크고, 해당 요소수가 비교할 값 보다 크면
                    a[j + h] = a[j]; //비교할 값이 있었던 자리에 j번째 요소값 넣기 그리고 j는 h만큼 이동후 j가 음수면 반복 종료
                }
                a[j + h] = tmp; // 집게로 뽑은 값을 비교한 j자리에 넣어준 것임(마지막에 j-=h를 실행하고 음수인 것을 확인하고 반복문을 종료하였기 때문)
            }
        }
    }

길이가 8인 배열에서 4-정렬은 이해가 가는데 이후 2-정렬이 이해가 어려워서 정리하는 글

1. a[2]은 a[0]과 비교해서 값이 크면 그대로 유지하고, 값이 작으면 교환됨(밑줄은 정렬이라 하겠음)
2. i값이 1증가 해서 a[3]은 a[1]값과 비교해서 정렬
3. i값이 1증가 해서 a[4]는 a[2]값과 비교해서 정렬, for문으로 a[2]값은 a[0]값과 비교해서 정렬, for문 종료
4. i값이 1증가 해서 a[5]는 a[3]값과 비교해서 정렬, for문으로 a[3]값은 a[1]값과 비교해서 정렬, for문 종료
5. i값이 1증가 해서 a[6]는 a[4]값과 비교해서 정렬, for문으로 a[4]값은 a[2]값과 비교해서 정렬, for문으로 a[2]값은 a[0]값과 비교해서 정렬, for문 종료
6. i값이 1증가 해서 a[7]는 a[5]값과 비교해서 정렬, for문으로 a[5]값은 a[3]값과 비교해서 정렬, for문으로 a[3]값은 a[1]값과 비교해서 정렬, for문 종료
7. 2-정렬 종료

결론적으로 2-정렬은 {a[0], a[2], a[4], a[6]} 의 정렬 + {a[1], a[3], a[5], a[7]}의 정렬