셸 정렬
보이기
(셸소트에서 넘어옴)
이 문서의 내용은 출처가 분명하지 않습니다. (2013년 5월) |
![]() 23, 10, 4, 1 갭(gap)이 있는 셸 정렬 | |
분류 | 정렬 알고리즘 |
---|---|
자료 구조 | 배열 |
최악 시간복잡도 | O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)[1] |
최선 시간복잡도 | O(n log n) (most gap sequences) O(n log2n) (best known worst-case gap sequence)[2] |
평균 시간복잡도 | 갭 시퀀스에 따라 |
공간복잡도 | О(n) 전체, O(1) 보조 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Shell_sorting_algorithm_color_bars.svg/220px-Shell_sorting_algorithm_color_bars.svg.png)
셸 정렬(영어: shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.
셸 정렬은 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있다.
- 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.
- 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다.
셸 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일(Subfile)이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다.
셸 정렬은 다음과 같은 과정으로 나눈다.
- 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.
- 데이터를 다시 잘게 나누어서 삽입 정렬한다.
- 이렇게 계속 하여 마침내 정렬이 된다.
셸 정렬에서 데이터를 나누는 값(이하 N)은 보통 전체에서 2로 나누는 값으로 진행한다. 그러나 3을 나누고 1을 더하는 경우가 더 빠르다고 알려져 있다. 즉 N/2 보다는 N/3+1이 더 빠르다.
알고리즘의 개요
[편집]- 자료리스트를 2차원배열로 나열한다.
- 각 배열의 열들을 정렬한다.
예제
[편집][2 5 3 4 3 9 3 2 5 4 1 3]로 리스트가 주어졌을 때 이 리스트를 셸 정렬로 정렬해 보자.
- 3행으로구성된 행렬로 나열하여 열단위로 정렬한다.
2 5 3 4 ⇒ 2 4 1 2 3 9 3 2 3 5 3 3 5 4 1 3 5 9 3 4 - 정렬된 3행 행렬을 6행렬로 나열하여 마찬가지로 열단위로 정렬한다.
2 4 ⇒ 1 2 1 2 2 3 3 5 3 4 3 3 3 4 5 9 3 5 3 4 5 9 -
정렬된 행렬을 한 열단위로 나열해서 삽입 정렬한다.
1 2 2 3 3 4 3 4 3 5 5 9 ⇒ 1 2 2 3 3 3 3 4 4 5 5 9 이 때, 자료가 멀리 이동될 필요가 없다는 장점이 있다.
소스 코드
[편집]def Shellsort(arr):
h = 1
while h < len(arr):
h = 3*h + 1
h = h//3
while h > 0:
for i in range(h,len(arr)):
k=i-h
key=arr[i]
while k>=0 and key < arr[k]:
arr[k+h] = arr[k]
k=k-h
arr[k+h] = key
h = h//3
return arr
public static void shellSort(Comparable[] array) {
//각 단계의 시작값
int[] cols = {1,5,12,23,62,145,367,815,1968,4711,11969,27901,84801,
213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647};
int c;
for (c = 0; cols[c] < array.length / 4; c++)
;
// 매개변수 값에 대한 순환
for (; c >= 0; c--) {
int step = cols[c];
for (int i = step; i < array.length; i++) {
Comparable m = array[i];
int j;
for (j=i; j>=step; j-=step) {
if (isLastBigger(array[j-step],m))
break;
array[j] = array[j-step];
}
array[j] = m;
}
같이 보기
[편집]각주
[편집]- ↑ Pratt, Vaughan Ronald (1979). 《Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)》. Garland. ISBN 978-0-8240-4406-0.[깨진 링크(과거 내용 찾기)]
- ↑ “Shellsort & Comparisons”. 2019년 12월 20일에 원본 문서에서 보존된 문서. 2019년 11월 20일에 확인함.
![]() |
이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |