자료구조
[자료구조] Shell Sort (셀 정렬)
J3SUNG
2021. 8. 6. 19:02
728x90
개념
간격을 기준으로 삽입정렬을 하는 방식
삽입정렬의 성질을 이용하고 보완한 방법
교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 더 높음
과정
1. 간격을 구합니다.
1.1) 현재 간격이 없는 경우 (개수 / 2)
1.2) 현재 간격이 있는 경우 (간격 / 2)
2. 간격들에 존재하는 수들끼리 삽입정렬
3. 간격이 1이 아닌 경우 1, 2 반복
4. 간격이 1인 경우, 정렬 완료
시간복잡도
Best Case = n
Average Case = n^1.5
Worst Case = n^2