셸 정렬(Shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.
셸 정렬은 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있다.
- 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.
- 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다.
셸 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일(Subfile)이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다.
셀정렬의 알고리즘은 아래와같다.
- 자료리스트를 2차원배열로 나열한다.
- 각 배열의 열들을 정렬한다.
[편집] 예제
[2 5 3 4 3 9 3 2 5 4 1 3]로 리스트가 주어졌을 때 이 리스트를 셸 정렬로 정렬해 보자.
1. 먼저 4열로 구성된 행열로 나열하여 열단위로 정렬한다.
2 5 3 4 2 4 1 2 3 9 3 2 -> 3 5 3 3 5 4 1 3 5 9 3 4
2. 정렬된 4열 행열을 2열 행열로 나열하여 마찬가지로 열단위로 정렬한다.
2 1 2 1 3 3 3 2 5 3 -> 4 3 4 2 5 3 5 3 5 3 9 4 9 4
3. 정렬된 2열 행열을 한 열단위로 나열해서 삽입 정렬한다. 여기서 장점은 자료가 멀리 이동될 필요가 없다는 것이다.
2 3 4 5 5 9 1 2 3 3 3 4 -> 1 2 2 3 3 3 3 4 4 5 5 9
[편집] 자바로 짠 원시코드
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; } } }
'Algorithm' 카테고리의 다른 글
| Sort.. algorithm (0) | 2008.09.09 |
|---|---|
| HDLC 프로토콜 (0) | 2008.08.26 |
| 삽입정렬 (0) | 2008.08.23 |
| 스케쥴링 (0) | 2008.08.19 |
| 선점,비선점 스케쥴링 (1) | 2008.08.19 |
