Study/Algorithm
정렬 알고리즘(3) - (쉘 정렬)
MWP
2017. 3. 12. 19:16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public static void sort(int[] arr){ int N = arr.length; int h = 1; // h 개 만큼 점프하면서 비교 while(h<N/3)h = h*3 +1; // 최적의 h 값을 구하는 공식 while(h >=1){ for(int i=h; i< N ; i++){ for(int j = i; j>=h && arr[j]<arr[j-h];j-=h){ // j를 인덱스로 h 만큼 접프하면서(j-=h) 비교한다. //인덱스 j 가 h보다 작으면 앞에 비교할 대상이 없다는 의미 int t = arr[j]; arr[j] = arr[j-h]; arr[j-h] = t; } } h/=3; // h 를 3으로 나누어준다 결국 h==1 이 될때 삽입정렬이 이루어짐 } } |
h 개 떨어진 원소들 간에 삽입정렬
의 수열을 사용한다
시간복잡도 :
공간복잡도 :
* 삽입정렬을 개선한 알고리즘 (삽입정렬보다 데이터 이동이 적다)
* 최선의 수열은 아직 발견되고 있지 않음
* 수열이 길면 단계 수 증가, 수열이 짧으면 성능 향상 정도가 미약 ( 성능이 h에 비례 )