[자료구조] Shell Sort (셀 정렬)

개념

간격을 기준으로 삽입정렬을 하는 방식

삽입정렬의 성질을 이용하고 보완한 방법
교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 더 높음

과정

1. 간격을 구합니다.
1.1) 현재 간격이 없는 경우 (개수 / 2)
1.2) 현재 간격이 있는 경우 (간격 / 2)
2. 간격들에 존재하는 수들끼리 삽입정렬
3. 간격이 1이 아닌 경우 1, 2 반복
4. 간격이 1인 경우, 정렬 완료

https://travelbeeee.tistory.com/215

 

https://travelbeeee.tistory.com/215

https://travelbeeee.tistory.com/215

 

시간복잡도

Best Case = n
Average Case = n^1.5
Worst Case = n^2