11. 쉘 정렬
알고리즘 공부
2019. 9. 29.
쉘정렬 삽입 정렬이 거의 정렬된 배열에서 최적의 성능을 내는 것에서 착안한 정렬 방법이다. 삽입 정렬을 띄엄띄엄한 간격으로 먼저 수행하고, 그 간격을 점차 좁혀나가면서 최종적으로는 거의 정렬된 배열을 삽입 정렬로 마무리하게 된다. 지저분해 보이지만 삽입 정렬의 특성을 잘 이용한 정렬로, 실제 성능은 힙 정렬 등에 버금갈 정도로 빠르다. 이 정렬 알고리즘의 핵심은 어떤 간격으로 정렬을 수행해 나갈 것이냐는 것인데, 간격에 따라 시간 복잡도도 제각각이다. 간격을 잘 선택하는 경우 까지도 가능하다고 하는데 일반적인 데이터 크기에 모두 적용할 수 있는 것은 아니다. 알고리즘 자체가 시간 복잡도가 명확하지 않고 퀵 정렬이나 병합 정렬에 비해 크게 나을 것이 없기에 일반적으로 쓰는 알고리즘은 아니다. 셸 정렬이란 ..
