셸 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

| 셸 정렬의 분석

셸 정렬의 2가지 장점

• 연속적이지 않은 부분 파일에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한 번에 한 칸씩만 이동된다. 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
  
• 부분 리스트가 하나가 되면 셸 정렬은 전체 리스트를 정렬해야 한다. 그러나 삽입 정렬이 거의 정렬된 리스트에 대해 매우 효율적이므로 이 과정도 빠르게 수행된다.

실험적인 연구를 통하여 셀 정렬의 시간 복잡도는 최악의 경우에는 이지만 평균적인 경우에는 인 것으로 알려져 있다.

---

// gap 만큼 떨어진 요소들을 삽입 정렬. 정렬의 범위는 first 에서 last

static void sortGapInsertion(int A[], int first, int last, int gap) {

int i, j, key;

for (i = first + gap; i <= last; i = i + gap) {

key = A[i];

for (j = i - gap; j >= first && key < A[j]; j = j - gap)

A[j + gap] = A[j];

A[j + gap] = key;

}

}

// 셸 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void shellSort(int A[], int n) {

for (int gap = n / 2; gap > 0; gap = gap / 2) {

printArray(A, n, "ShellSort"); // 처리과정을 보기 위한 코드

if ((gap % 2) == 0) gap++;

for (int i = 0; i < gap; i++) // 부분 리스트의 개수는 gap

sortGapInsertion(A, i, n - 1, gap);

}

}