셸 정렬이란? 삽입정렬을 보완한 알고리즘이다. - 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안 - 삽입 정렬의 최대 문제점: 요소들이 삽입될 때, 이웃한 위치로만 이동 - 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. - 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때, k를 ‘간격(gap)’ 이라고 한다. - 간격의 초깃값: (정렬할 값의 수)/2 - 생성된 부분 리스트의 개수는 gap과 같다. 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 ..
