쉘 정렬 (Shell Sort)

쉘 정렬 (Shell Sort)

• 원소의 비교 연산과 먼 거리의 이동을 줄이기 위해 몇 개의 서브 리스트로 나누어 삽입 정렬을 반복 수행
• 삽입 정렬의 개념을 확대하여 일반화 시킨 정렬 방법
• 삽입 정렬의 최대 문제점 : 요소들이 이동할 때, 이웃한 위치로만 이동하는 것
• 쉘 정렬 -> 요소들이 멀리 떨어진 위치로도 이동할 수 있기 때문에 쉘 정렬이 삽입 정렬보다 정렬 속도 빠름

쉘 정렬 방법

• 정렬에서 사용할 간격(interval) 결정
  • 전체 원소 수 n의 1/3, 다시 이것의 1/3, …
  • 간격이 작아질수록 짧은 거리를 이동하고 원소 이동이 적음
• 첫 번째 간격에 따라 서브 리스트로 분할
  • 각 서브 리스트에 대해 삽입 정렬 수행
• 두 번째 간격에 따라 서브 리스트로 분할
  • 각 서브 리스트에 대해 삽입 정렬 수행
• 리스트 전체에 대해 삽입 정렬 수행 (마지막 간격은 1)

쉘 정렬 예제

package sort;

public class ShellSortEx {

	public static void main(String[] args) {
		int[] arr = {10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16};
		shellSort(arr);
		
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i] + " ");
		}

	}
	
	static void shellSort(int[] arr) {
		int N = arr.length;
		
		for(int h=N/2; h > 0; h/=2) {
			//System.out.println(h); // 간격 h 확인
			for(int i=h; i<N; i++) { // 삽입 정렬을 하기 위해 서브 리스트의 두 번째 값을 가지고 값을 비교
				int index = i-h;
				
				int temp = arr[i]; 
				
				// 삽입 정렬 수행
				while(index >=0 && arr[index] > temp) {
					arr[index+h] = arr[index];
					index -= h;
				}
				
				arr[index + h] = temp;
			}
			
			// 각 간격마다 정렬 결과 (5간격 / 2간격 / 1간격)
			for(int a : arr) {
				System.out.print(a + " ");
			}
			System.out.println();
		}
	}

}