쉘 정렬이란?
쉘 정렬(Shell Sort)은 삽입 정렬을 확장·개선한 비교 기반 정렬 알고리즘입니다. 쉘 정렬을 구현하려면 먼저 하나의 함수를 정의하는데, 이 함수는 리스트와 리스트의 길이를 인자로 받습니다. 리스트는 특정 간격(interval)만큼 떨어져 있는 요소들끼리 먼저 정렬되며, 간격은 가장 큰 값에서 시작해 반복할 때마다 절반씩 줄어들어 최솟값인 1에 도달할 때까지 이 과정이 진행됩니다.
이러한 정렬 작업은 리스트 안의 모든 부분 리스트(sub-list)에 대해 수행되며, 간격이 1이 되면 사실상 일반적인 삽입 정렬과 동일하게 동작하여 전체 리스트가 완전히 정렬됩니다.
참고로 파이썬의 리스트는 서로 다른 자료형의 값을 함께 저장할 수 있습니다. 즉, 정수, 실수, 문자열 등 어떤 데이터 타입이든 하나의 리스트에 담아 처리할 수 있습니다.
아래는 쉘 정렬을 구현한 예시입니다.
예제
def shell_sort(my_list, list_len):
interval = list_len // 2
while interval > 0:
for i in range(interval, list_len):
temp = my_list[i]
j = i
while j >= interval and my_list[j - interval] > temp:
my_list[j] = my_list[j - interval]
j -= interval
my_list[j] = temp
interval //= 2
my_list = [ 45, 31, 62, 12, 89, 5, 9, 8]
list_len = len(my_list)
print ("정렬 전 리스트 :")
print(my_list)
shell_sort(my_list, list_len)
print ("\n쉘 정렬 수행 후 리스트 :")
print(my_list)
출력
정렬 전 리스트 :
[45, 31, 62, 12, 89, 5, 9, 8]
쉘 정렬 수행 후 리스트 :
[5, 8, 9, 12, 31, 45, 62, 89]
동작 원리
- 'shell_sort'라는 이름의 메서드가 정의되며, 리스트와 리스트의 길이를 인자로 받습니다.
- 'interval' 변수는 '//' 연산자를 사용해 정의됩니다.
- '//'는 바닥 나눗셈(floor division)을 수행합니다.
- 바닥 나눗셈은 소수점 이하를 버리고 가장 가까운 정수로 내림합니다.
- 리스트를 순회하면서 현재 요소를 저장할 임시 변수(temp)를 생성합니다.
- 간격(interval)만큼 떨어진 요소들을 서로 비교하며, 필요한 경우 위치를 교환합니다.
- 내부 반복이 끝나면 'interval' 변수는 다시 바닥 나눗셈을 통해 절반으로 줄어듭니다.
- 리스트를 정의한 뒤 콘솔에 출력합니다.
- 리스트와 그 길이를 인자로 전달하여 'shell_sort' 메서드를 호출합니다.
- 정렬된 결과가 콘솔에 출력됩니다.
시간 복잡도 참고
쉘 정렬의 성능은 사용하는 간격(gap) 수열에 따라 달라집니다. 위 예제처럼 간격을 절반씩 줄이는 방식의 경우 최악의 시간 복잡도는 O(n²)이지만, 적절한 간격 수열을 사용하면 평균적으로 O(n log²n) 수준의 성능을 기대할 수 있습니다. 또한 제자리(in-place) 정렬이므로 추가적인 메모리 사용량이 거의 없다는 장점도 있습니다.