insert sort는 바로 앞에꺼와 비교했다면
shell sort 는 바로 앞이 아닌 인터벌을 두고 비교
저 뒤에 잘못 배치된 놈이 한방에 제자리로 갈수도 있는 효율적 상황을 기대해 보자!
고로 비교 간격 설정부터!
Donald Shell은 처음에 간격을 2^k, (k는 0 이상의 자연수) 혹은 2^k-1로 잡았으며,
Marcin Ciura의 연구에 의하면 1, 4, 10, 23, 57, 132, 301, 701, 1750 ... 과 같은 간격을 사용하는 것이
연산 시간을 많이 줄인다고 한다.
참고사이트2
h(1) = 1;
h(i+1) = 3* h(i) + 1; 을 거쳐 나온 1, 4, 13, 40, 121, 364, 1093, 3280...순
잘 알려진 optimal sequence로 다음 두 가지를 알아두자.
1. Sedgewick : 1 3 7 21 48 112 336 861 1968 4592
2. Papernov-Stasevic : 1 3 7 15 31 63 127 255 511 1023 2047
여기서는 비교간격 k = n/2 = 9/2 = 4
1 7 2 8 6 9 3 5 4
>Step 1 ( k=4 )
1 7 2 8 // 6 9 3 5 // 4 -> 1 과 6 비교 바꿀 필요 없음
1 7 2 8 // 6 9 3 5 // 4 -> 6 과 4 비교 바꿈
1 7 2 8 // 4 9 3 5 // 6
1 7 2 8 // 4 9 3 5 // 6 -> 7 과 9 비교 바꿀 필요 없음
1 7 2 8 // 4 9 3 5 // 6 -> 2 과 3 비교 바꿀 필요 없음
1 7 2 8 // 4 9 3 5 // 6 -> 8 과 5 비교 바꿈
1 7 2 5 // 4 9 3 8 // 6
>Step 2 ( k=2 )
1 7 // 2 5 // 4 9 // 3 8 // 6 -> 1 과 2 비교 바꿀 필요 없음
1 7 // 2 5 // 4 9 // 3 8 // 6 -> 2 과 4 비교 바꿀 필요 없음
1 7 // 2 5 // 4 9 // 3 8 // 6 -> 4 과 3 비교 바꿈1 7 // 2 5 // 3 9 // 4 8 // 6
1 7 // 2 5 // 3 9 // 4 8 // 6 -> 4 과 6 비교 바꿀 필요 없음
1 7 // 2 5 // 3 9 // 4 8 // 6 -> 7 과 5 비교 바꿈
1 5 // 2 7 // 3 9 // 4 8 // 6
1 5 // 2 7 // 3 9 // 4 8 // 6 -> 7 과 9 비교 바꿀 필요 없음
1 5 // 2 7 // 3 9 // 4 8 // 6 -> 9 과 8 비교 바꿈
1 5 // 2 7 // 3 8 // 4 9 // 6
>Step 3 ( k=1 ) !! 여기서 부터는 Insert Sort
1 5 2 7 3 8 4 9 6 -> 1 과 5 비교 바꿀 필요 없음
1 5 2 7 3 8 4 9 6 -> 5 과 2 비교 바꿈
1 2 5 7 3 8 4 9 6
1 2 5 7 3 8 4 9 6 -> 1 과 2 비교 바꿀 필요 없음
1 2 5 7 3 8 4 9 6 -> 5 과 7 비교 바꿀 필요 없음
1 2 5 7 3 8 4 9 6 -> 7 과 3 비교 바꿈
1 2 5 3 7 8 4 9 6
1 2 5 3 7 8 4 9 6 -> 5 과 3 비교 바꿈
1 2 3 5 7 8 4 9 6
1 2 3 5 7 8 4 9 6 -> 2 과 3 비교 바꿀 필요 없음
다음은 8 그 다음은 4 그 다음은 9 순으로 비교
참고 영상 링크
영상은 스타일이 좀 다릅니다
댓글 없음:
댓글 쓰기