📚 셸 정렬

셸 정렬

정렬 방법

1. 간격(gap)을 설정한다.
2. 각 간격 별로 분류된 서브(부분) 리스트에 대해 삽입정렬을 한다.
3. 각 서브(부분) 리스트의 정렬이 끝나면 간격을 줄인다.
4. 간격이 1이 될 때 까지 2번 과정으로 되돌아가며 반복한다.

🤔 그럼 간격(gap)은 어떻게 설정해요? 😲 답은 없다.

왜냐하면 간격(gap)이 너무 적으면 건너 뛰는 간격이 좁아진다. 즉, pass 속도가 느려진다는 뜻이다.

반대로 간격이 크면 오버헤드가 발생한다.

그래서 많은 사람들이 평균적으로 좋은 간격들을 내놓았는데, 이를 갭 시퀀스(Gap Sequences)라고 한다.

아래 글을 보면 많은 갭 시퀀스들이 있다는 것을 볼 수 있다.
Shellsort

셸 정렬의 특징

📚 삽입 정렬은 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.

연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높아진다.

부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행된다.

시간복잡도

• 평균: T(n) = O(n^1.5)
• 최악의 경우: T(n) = O(n^2)

구현

• 사용 시퀀스: Ciura 시퀀스

  • gap Sequence = {1, 4, 10, 23, 57, 132, 301, 701, 1750}

  • 1750 이후로는 Gn = (Gn - 1) * 2.25 로 표현

  • 정리하면 다음과 같다

    private final static int[] gap = 
    		{ 1, 4, 10, 23, 57, 132, 301, 701, 1750, 3937, 	
    		8858, 19930, 44842, 100894, 227011, 510774,
    		1149241, 2585792, 5818032, 13090572, 29453787, 
    		66271020, 149109795, 335497038, 754868335, 1698453753};	// 갭을 담고있는 배열

• 1️⃣ 삽입 정렬을 포함한 구현

  public class Shell_Sort {
  	
  	private final static int[] gap = 
  		{ 1, 4, 10, 23, 57, 132, 301, 701, 1750, 3937, 	
  		8858, 19930, 44842, 100894, 227011, 510774,
  		1149241, 2585792, 5818032, 13090572, 29453787, 
  		66271020, 149109795, 335497038, 754868335, 1698453753};	// 갭을 담고있는 배열	
   
  	
  	public static void shell_sort(int[] a) {
  		shell_sort(a, a.length);
  		
  	}
   
  	// 맨 처음 gap을 참조할 인덱스를 구하는 메서드
  	private static int getGap(int length) {
  		int index = 0;
  		// 최소한 부분 배열의 원소가 2개씩은 비교되도록 나눠준다.
  		int len = (int)(length / 2.25);	// → Gn = (Gn - 1) * 2.25
  		while (gap[index] < len) {
  				index++;
  		}
  		return index;
  	}
   
  	private static void shell_sort(int[] a, int size) {
  		int index = getGap(size);	// 첫 gap을 사용할 index
   
  		// gap[index] 값부터 gap[0] 까지 반복한다.
  		for (int i = index; i >= 0; i--) { 
  			for (int j = 0; j < gap[i]; j++) {
  				insertion_sort(a, j, size, gap[i]);	// 각 부분 리스트에 대해 삽입정렬을 한다.
  			}
  		}
  	}
   
  	/**
  	 * @param a		   배열
  	 * @param start	 부분 배열의 첫 번째 원소 인덱스 
  	 * @param size	 배열의 전체 크기
  	 * @param gap	   현재 gap
  	 */
  	private static void insertion_sort(int[] a, int start, int size, int gap) {
   
  		// 부분 배열의 두 번째 원소부터 size까지 반복한다. (gap 값씩 건너띔) 
  		for (int i = start + gap; i < size; i += gap) {
   
  			int target = a[i];
  			int j = i - gap;
   
  			// 타겟 원소가 이전의 원소보다 작을 때 까지 반복 
  			while (j >= start && target < a[j]) {
  					a[j + gap] = a[j];	// 이전 원소를 한 칸씩 뒤로 미룬다.
  					j -= gap;
  			}
  			/*
  			 * 위 반복문에서 탈출 하는 경우 앞의 원소가 타겟보다 작다는 의미이므로
  			 * 타겟 원소는 j번째 원소 뒤에 와야한다.
  			 * 그러므로 타겟은 j + gap 에 위치하게 된다.
  			 */
  			a[j + gap] = target;
   
  		}
  	}
  }

• 2️⃣ 삽입 정렬을 제외한 구현

  public class Shell_Sort {
  	
  	private final static int[] gap = 
  		{ 1, 4, 10, 23, 57, 132, 301, 701, 1750, 3937, 	
  		8858, 19930, 44842, 100894, 227011, 510774,
  		1149241, 2585792, 5818032, 13090572, 29453787, 
  		66271020, 149109795, 335497038, 754868335, 1698453753};	// 갭을 담고있는 배열	
   
  	
  	public static void shell_sort(int[] a) {
  			shell_sort(a, a.length);
  	}
   
  	// 맨 처음 gap을 참조 할 인덱스를 구하는 메소드
  	private static int getGap(int length) {
  			int index = 0;
  			// 최소한 부분 배열의 원소가 2개씩은 비교 되도록 나눠준다.
  			int len = (int)(length / 2.25);	
  			while (gap[index] < len) {
  				index++;
  			}
  			return index;
  	}
  	
   	private static void shell_sort(int[] a, int size) {
  			int gapIndex = getGap(size);
  		
  			// 갭이 1이 될 때까지 반복
  			while(gapIndex >= 0) {
  					int step = gap[gapIndex--];	// 현재 gap(step)
  					/*
  					 * <--- 삽입 정렬 과정 --->
  					 * 
  					 *  각 부분리스트의 두 번째 원소의 인덱스 부터 순회한다.
  					 *  예를 들어, step이 3일 때 arr[0], arr[1], arr[2] 는 
  					 *  이전 원소와 비교할 것이 없다.
  					 *  그러므로 step부터 순회한다.   
  					 */
  					for(int i = step; i < size; i++) {				
  							/*
  							 *  j는 target 원소가 되며 현재 원소(target) a[j]가 이전 원소 a[j - step]보다
  							 *  작을 때 까지 반복한다.
  							 */
  							for (int j = i; j >= step && a[j] < a[j - step]; j -= step) {
  									/*
  									 *  현재(target) 원소의 인덱스(j)와 이전의 원소(j-step)의 인덱스에 있는
  									 *  원소의 값을 교환한다.
  									 */
  									swap(a, j, j - step);
  							}
  					}
  			}
  	}
   
  	private static void swap(int[] a, int i, int j) {
  			int swap = a[i];
  			a[i] = a[j];
  			a[j] = swap;
  	}
  }

참고
[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog
자바 [JAVA] - 셸 정렬 (Shell Sort)