[Java 실습] 셸 정렬(Shell Sort)

셸 정렬은 단순 삽입 정렬의 장점을 살리고, 단점을 보완하여 좀 더 빠르게 정렬하는 알고리즘입니다.

---

다음은 셸 정렬을 오름차순으로 정렬한 코드입니다.

 

마지막 1-정렬은 삽입 정렬과 다르지 않습니다.

public class shellSort {
	
	static void shellSort(int[] arr) {
		// 4-정렬, 2-정렬, 1-정렬 범위를 정해줌
		// 마지막 1-정렬은 삽입 정렬(insertion sort)과 같음
		for(int i=arr.length/2; i>0; i/=2) {
			for(int j=i; j<arr.length; j++) {
				int k=0;
				// temp에 비교할 값 잠시 저장
				int temp = arr[j];
				// ex) 2-정렬
				// temp=5 기준으로 하면 3,5 다음 0,5 비교.. (k-=i를 통해)
				for(k=j-i; k>=0 && arr[k]>temp; k-=i) {
					arr[k+i] = arr[k];
				}
				arr[k+i] = temp;
			}
		}
	}
	public static void main(String[] args) {
		int [] arr = new int[] {8,2,4,5,7,9,11,6};
		
		shellSort(arr);
			
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}

셸 정렬은 개인적으로 머리로는 알고리즘을 알겠으나, 코드로 구현하기 어려워

 

Do it! 자바 자료구조 알고리즘 책에 있는 코드를 통해 이해하였습니다.

---

사진 출처 : https://t1.daumcdn.net/cfile/tistory/223DFC4B5451F3590A

코드 출처 : http://easyspub.co.kr/20_Menu/BookView/257/PUB