셸 정렬 알고리즘이란?

오늘은 정렬 알고리즘 중 삽입 알고리즘의 단점을 개선한 알고리즘인 셸 정렬 알고리즘에 대해 소개하려고 한다

참고로 셸 정렬이 셸 정렬인 이유는 이 알고리즘을 처음 제안한 Donald L. Shell의 이름에서 따와 붙여졌기 때문이다

셸 정렬이란?

셸 정렬은 기본적인 로직으로 삽입 정렬을 사용하지만 일정한 간격을 두고 요소들을 정렬하며 이 간격을 점차 줄여가면서 전체 리스트를 정렬하는 방식으로

삽입 정렬을 확장하여 삽입 정렬이 가지고 있던 문제인 대규모의 데이터 집합이 느리다는 것을 효과적으로 정렬할 수 있게 해결하였다

셸 정렬의 작동 방식

글로만 보면 어렵게 느껴질 수 있으므로 예시를 통해 설명해보자

정렬해야 하는 리스트:

[35, 33, 42, 10, 14, 19, 27, 44]

먼저 셸 정렬의 첫 단계는 ‘간격’을 정하는 것이다 예를 들어 길이가 8인 이 배열에서 간격 4로 시작할 수 있다

이 간격에 따라 서브 리스트를 만들면 아래와 같다

[35, 14]
[33, 19]
[42, 27]
[10, 44]

이제 해당 서브 리스트를 삽입 정렬로 정렬한고

이후 간격을 줄여서 다시 정렬하는 과정을 반복하면 된다 다음은 간격을 2로 줄여보자

[14, 42, 10, 44]
[19, 27, 35, 33]

마지막으로 간격을 1로 줄여서 전체 배열에 대해 삽입 정렬을 진행하면 완전히 정렬된 배열이 완성된다

셸 정렬의 장단점

마지막으로 셸 정렬 알고리즘에 장단점을 알아보자

장점:

1. 중간 크기의 배열에서 효과적이다
2. 삽입 정렬보다 일반적으로 더 빠르다
3. 인플레이스 정렬이기 때문에 추가 메모리가 필요하지 않다

단점:

1. 간격 선택에 따라 성능이 크게 달라질 수 있다
2. 코드가 다소 복잡하다.