셸 정렬(Shell Sort)

셸 정렬(Shell Sort)

일정한 간격인 원소들끼리 부분집합으로 묶어 삽입 정렬을 수행하는 작업을 반복하면서 정렬. 삽입 정렬보다 비교, 교환 연산을 줄일 수 있다.

일정한 간격은 매개 변수로 받으며 일반적으로 전체 원소 수의 1/2로 설정하고, 단계를 반복할 때마다 절반으로 감소시키면서 반복한다.

​

매개변수의 영향으로 인해 성능 분석이 쉽지 않지만 일반적으로 시간 복잡도를 O(n^1.25)로 측정한다.

​

예시)

{57, 16, 41, 2, 50, 6, 32, 27}

​

1. 일정한 간격을 원소 수의 절반인 4로 설정하고 그에 해당하는 부분집합끼리 삽입 정렬을 수행한다.

{57, 16, 41, 2, 50, 6, 32, 27}

===> 57과 50을 삽입 정렬

{50, 16, 41, 2, 57, 6, 32, 27}

===> 16과 6을 삽입 정렬

{50, 6, 41, 2, 57, 16, 32, 27}

===> 41과 32를 삽입 정렬

{50, 6, 32, 2, 57, 16, 41, 27}

===> 2와 27을 삽입 정렬(제자리)

{50, 6, 32, 2, 57, 16, 41, 27}

​

2. 간격을 4의 절반인 2로 설정하고 위의 작업을 수행한다.

{50, 6, 32, 2, 57, 16, 41, ​27}

===> 50, 32, 57, 41을 삽입 정렬

{32, 6, 41, 2, 50, 16, 57, 27}

===> 6, 2, 16, 27을 삽입 정렬

{32, 2, 41, 6, 50, 16, 57, 27}

​

3. 간격을 2의 절반인 1로 설정하고 위의 작업을 수행한다.(전체 원소에 대하여 삽입 정렬)

삽입 정렬 글 참고

S = {32}, U = {2, 41, 6, 50, 16, 57, 27}

===>

S = {2, 32}, U = {41, 6, 50, 16, 57, 27}

===>

S = {2, 32, 41}, U = {6, 50, 16, 57, 27}

===>

S = {2, 6, 32, 41}, U = {50​, 16, 57, 27}

===>

S = {2, 6, 32, 41, 50}, U = {16, 57, 27}

===>

S = {2, 6, 16, 32, 41, 50}, U = {57, 27}

===>

S = {2, 6, 16, 32, 41, 50, 57}, U = {27}

===>

S = {2, 6, 16, 27, 32, 41, 50, 57}, U = {}

​

프로그램 작성)

 

package test;

class Sort {
	public void shellSort(int[] a, int size) {
		int i, interval;
		interval = size / 2;
		
		while(interval >= 1) {
			for(i=0; i<interval; i++) {
				intervalInsertSort(a, i, size-1, interval);
			}
			
			interval /= 2;
		}
	}
	
	// 간격(interval) 별 삽입 정렬
	public void intervalInsertSort(int a[], int start, int end, int interval) {
		int i, j, temp;
		
		for(i=start+interval; i<=end; i=i+interval) {
			temp = a[i];
			for(j=i-interval; j>=start && temp<a[j]; j=j-interval) {
				a[j+interval] = a[j];
			}
			
			a[j+interval] = temp;
		}
	}
}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6, 32, 27};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.shellSort(a, a.length);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)