[Data Structure] 쉘 정렬 - Shell Sort

쉘 정렬 (Shell Sort) Unstable Sort 정렬할 리스트의 간격에 따라서 각 부분 리스트를 정렬하는 정렬 알고리즘 간격(gap) = 리스트/2/2/2,...... → 계속해서 2로 나눠준다 (1이 될 때 까지) 만약 gap이 짝수이면 1을 더해준다 (간격이 홀수이면 더 성능이 좋다) 부분 리스트의 개수는 gap과 동일하다 보통 전체에서 h/2를 하지만 이보다 h/3 + 1 이 더 빠르다 시간복잡도 - 최선 : O(n) - 평균/최악 : O(n1.5) 장점 - Insertion Sort의 단점을 보완하고 개념을 확대해서 만든 정렬 - Insertion Sort보다 성능이 우수하다 - 데이터가 본인의 index에서 멀리 떨어져 있을 경우, 교환을 여러번하는 Bubble Sort의 단점을 해결 ..

2022.01.01