레퍼런스 마이닝

셸 정렬 기본 개념 "Donal L. Shell"이라는 사람이 제안한 방법으로, 삽입 정렬을 보안한 알고리즘이다. 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 빠르다는 것을 착안하였다. 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 셸 정렬 구체적인 개념 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때 k를 "간격(gap)"이라고 한다. 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다. 간격의 초기값 : 정렬할 리스트 사이즈 / 2 분할된 리스트의 개수는 gap과 같다. 간격은 홀수로 하는 것이 좋다. 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수를 만든다. 간격 ..