1. 셸 정렬(Shell Sort)?
셸 정렬은 삽입 정렬의 단점인 원소를 적합한 위치에 삽입하기 위해 원소들을 뒤로 옮기는 과정을 줄이기 위해, 특정한 거리씩 떨어진 원소들끼리 삽입정렬을 하고, 그 거리을 차츰 줄여나가면서, 최종적으로는 전체 원소들에 대해 삽입정렬을 하는 알고리즘입니다.
※ 삽입 정렬에 대한 내용은 정렬 알고리즘(Sort Algorithm) (4) - 삽입 정렬(Insertion Sort)(http://jufafa.blogspot.kr/2015/09/sort-algorithm-4-insertion-sort.html)를 참조해주세요.
2. 예시
5
|
1
|
9
|
3
|
7
|
8
|
데이터를 가지고 직접 셸 정렬을 해봅시다. (여기서는 원소간 거리가 3, 1로 줄어드는 경우로 합니다.)
1. 거리가 3만큼 떨어진 원소끼리 삽입 정렬을 한다.
5
|
1
|
9
|
3
|
7
|
8
|
5
|
1
|
9
|
5
|
7
|
8
|
3
|
1
|
9
|
5
|
7
|
8
|
3
|
1
|
9
|
5
|
7
|
8
|
3
|
1
|
9
|
5
|
7
|
8
|
3
|
1
|
9
|
5
|
7
|
8
|
3
|
1
|
8
|
5
|
7
|
9
|
3
|
1
|
8
|
5
|
7
|
9
|
2. 거리가 1만큼 떨어진 원소끼리 삽입 정렬을 한다.
3
|
1
|
8
|
5
|
7
|
9
|
3
|
3
|
8
|
5
|
7
|
9
|
1
|
3
|
8
|
5
|
7
|
9
|
1
|
3
|
8
|
5
|
7
|
9
|
1
|
3
|
8
|
5
|
7
|
9
|
1
|
3
|
8
|
5
|
7
|
9
|
1
|
3
|
8
|
8
|
7
|
9
|
1
|
3
|
5
|
8
|
7
|
9
|
1
|
3
|
5
|
8
|
7
|
9
|
1
|
3
|
5
|
8
|
8
|
9
|
1
|
3
|
5
|
7
|
8
|
9
|
1
|
3
|
5
|
7
|
8
|
9
|
1
|
3
|
5
|
7
|
8
|
9
|
1
|
3
|
5
|
7
|
8
|
9
|
3. 특징
셸정렬은 인접한 원소간의 정렬이 아닌 떨어진 원소간의 정렬로 인해 같은 우선순위를 갖는 원소간의 순서가 보존되지 않는다.
4. C를 이용한 구현
다음 코드는 원소간 거리를 데이터의 절반에서 부터 시작하여, 정렬이 완료될 때까지 반으로 나눠가는 방법을 사용하였다.
4. 원소간 거리를 어떻게 정해야 하는가?
셸 정렬의 기본전략은 삽입정렬 과정에서 원소를 뒤로 옮기는 횟수를 줄이는 것으로 속도를 향상시키는데 있다. 하지만, 삽입정렬 횟수가 너무 많거나, 적게 된다면, 이러한 효과가 떨어진다. 때문에 원소간 거리에 대한 최적화된 수열을 사용한다면 속도를 더욱 향상시킬 수 있게된다.
댓글 없음:
댓글 쓰기