📌 쉘 정렬
: 삽입 정렬을 확장한 것
- 멀리 떨어진 원소를 교환하여 속도를 빠르게 한 것
- 부분 배열의 (삽입)정렬이 끝나고 난 후 전체 (삽입)정렬을 적용
🔎
1. n개의 키가 저장되어 있는 배열을 n/3개씩 부분 배열로 나눈다.
2. 각 부분 배열은 거리가 n/3씩 떨어져 있는 원소들로 구성함
3. 각 부분 배열에서 삽입 정렬을 함
4. 각 부분 배열에서 삽입 정렬을 끝낸 후 전체 배열에서 다시 삽입 정렬을 적용함
❗ 쉘 정렬의 특징
- 순열 h가 1, 4, 13, 40, ... 일 때, 쉘 정렬의 비교 횟수는 n⅔을 넘지 않음
- 제자리 정렬이지만 불안정함
