셸 정렬(Shell Sort)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① 셸 정렬(shell sort)는 삽입 정렬의 일반화된 형태이며, 먼 거리에 있는 요소들 간의 교환을 가능하게 해서 성능을 높였다.

  ㉠ 셸 정렬은 셸의 방법(shell 's method)으로도 불린다.

② 셸 정렬의 최악의 시간 복잡도는 삽입 정렬과 마찬가지로 O(log(n))이다.

  ㉠ 그렇지만, 퀵 정렬 다음으로 셸 정렬이 두 번째로 빠르다.

③ 셸 정렬의 기본 원리는 다음과 같다.

  ㉠ 정수로 된 갭 시퀀스를 정한다. (h1>h2>h3>h4>...hk = 1)

    ⓐ 갭은 하위 배열 간의 간격을 의미하며, 최종적으론 하위 정렬 간의 간격이 1이 되어야 함을 의미한다.

 

상대적으로 구현하기 쉬운 것은 2번이다.

    ⓑ 갭이 1씩 줄어드는 갭 시퀀스를 가진 셸 정렬이 삽입 정렬이다.

 

삽입 정렬(Insertion Sort)과 이진 삽입 정렬(Binary Insertion Sort)

  ㉡ 현재 갭으로 하위 배열을 분할하고, 하위 배열을 삽입 정렬로 정렬한다.

 

  ㉢  최종적으로는 갭의 크기가 1이 될 떄까지 ㉡을 수행한다.

④ 셸 정렬의 의사 코드(psuedo code)는 다음과 같다.

 

⑤ 셸 정렬의 구현 코드는 다음과 같다.

 

⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮
㉠㉡㉢㉣㉤㉥㉦㉧㉨㉩㉪㉫㉬㉭
ⓐⓑⓒⓓⓔⓕⓖⓗⓘⓙⓚⓛⓜ