쉘 정렬 (shell sort)

주제(Subject)
--------------------------------------------------------
한글(약어) : 쉘 정렬()
영어(약어) : shell sort()


관련개념(Related Concepts)
--------------------------------------------------------
정렬
삽입정렬
알고리즘


개요(Summary)
--------------------------------------------------------
- Donald Shell이 고안한 알고리즘
- 삽입정렬 알고리즘의 단점 보완
- 불안정적
- 제자리 정렬
 

본문(Body)
--------------------------------------------------------
1. 알고리즘
   1) 입력배열을 부분배열로 나누어 정렬함
   2) 순서에 맞지 않는 키들을 빠르게 장거리 이동시키도록 고안됨
   3) 알고리즘의 효율성

Depending on the choice of gap sequence, Shellsort has a proven worst-case running time of O(n²) (using Shell's increments that start with 1/2 the array size and divide by 2 each time), O(n^{3 / 2}) (using Hibbard's increments of 2^k − 1), O(n^{4 / 3}) (using Sedgewick's increments of 9(4ⁱ) − 9(2ⁱ) + 1, or 4^{i + 1} + 3(2ⁱ) + 1), or O(nlog²n), and possibly unproven better running times. The existence of an O(nlogn) worst-case implementation of Shellsort remains an open research question.  
                                                                                 - from Wikipedia : Shell Sort

2. 소스코드
   1) C/C++ (from Wikipedia : Shell Sort)

void shell_sort(int A[], int size)
{
  int i, j, incrmnt, temp;

  incrmnt = size / 2;
  while (incrmnt > 0)
  {
    for (i=incrmnt; i < size; i++)
    {
      j = i;
      temp = A[i];
      while ((j >= incrmnt) && (A[j-incrmnt] > temp))
      {
        A[j] = A[j - incrmnt];
        j = j - incrmnt;
      }
      A[j] = temp;
    }
    incrmnt /= 2;
  }
}

3. 시뮬레이션
   1) Graphical Java Applet Version
   http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shell.htm
   2) User can input numerical data
   http://www.wanginator.de/studium/applets/shellsort_en.html


모임,단체(Commutities)
--------------------------------------------------------


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------
1. Robert Sedgewick (Department of Computer Science, Princeton University, Princeton)
   http://www.cs.princeton.edu/~rs/


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Sequentielle und parallele Sortierverfahren(Medieninformatik und Technische Informatik)
   http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/

2. D.L. Shell: A High-Speed Sorting Procedure. Communications of the ACM, 2, 7, 30-32 .1959.

3. Java Animations of Shellsort and variants by Robert D. Sedgewick
   http://www.cs.princeton.edu/~rs/shell/animate.html

4. Wikipedia : Shell Sort
   http://en.wikipedia.org/wiki/Shell_sort