쉘 정렬(Shell Sort)
삽입 정렬의 장점은 살리면서 단점은 보완한 알고리즘
삽입 정렬의 최대 문제점
- 요소들이 삽입될 때, 이웃한 위치로만 이동 -> 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있음.
- 쉘 정렬은 삽입 정렬과 다르게 전체의 리스트를 한 번에 정렬하지 않음
구현 방식
- 정렬할 배열을 일정한 기준(간격)에 따라 분류
- 각 부분 배열을 삽입 정렬로 정렬
- 다시 전체 배열을 더 적은 개수의 부분 배열로 분류
- 위 2번째 3번째 과정을 부분 배열의 길이가 1이 될 때까지 반복한다.
시간복잡도는 최적 O(n), 평균 O(n^1.5), 최악 O(n^2)
공간복잡도 O(n)
장점
- 연속적이지 않은 리스트의 자료 교환이 일어나면 더 큰 거리를 이동 -> 따라서 교환되는 요소들이 삽입 정렬보다 최종 위치에 있을 가능성 높음
- 삽입 정렬, 거품 정렬에 비해 정렬 속도가 빠르다
- 간격 시퀀스가 좋을 경우 O(nlogn) 정도로 좋은 속도 보장
단점
- 삽입 정렬에 비해 구현이 어려움
- 간격 시퀀스에 영향을 많이 받으며 적절한 시퀀스를 선택해야함
- 일정 간격을 두고 교환이 이루어지기에 안정 정렬이 아니다
너무 소심하고 까다롭게 자신의 행동을 고민하지 말라 . 모든 인생은 실험이다 . 더많이 실험할수록 더나아진다. – 랄프 왈도 에머슨
오늘한줄.