0. [사전 지식] 삽입 정렬
1. 쉘 정렬이란?
쉘 정렬(Shell Sort)은 삽입 정렬의 일반화된 형태로, 데이터 배열을 일정 간격(gap)으로 나누어 부분적으로 정렬한 후, 간격을 점차 줄여가며 최종 정렬을 완성하는 알고리즘입니다. 데이터의 크기가 클수록 삽입 정렬의 비효율성을 줄여주는 것이 특징입니다.
2. 원리
- 배열의 요소를 일정한 간격으로 그룹화합니다.
- 각 그룹 내에서 삽입 정렬을 수행합니다.
- 간격을 점차 줄이며 과정을 반복합니다.
- 간격이 1이 되면 최종적으로 전체 배열을 삽입 정렬합니다.
쉘 정렬의 핵심은 초기에는 큰 간격을 사용해 멀리 떨어진 요소들 간의 정렬을 수행하고, 간격을 줄여가며 점진적으로 정렬을 세밀화한다는 점입니다.
일반적으로 간격은 초기 간격을 (배열 원소 개수 / 2)으로 계산하고, 간격을 줄여나갑니다. 최종적으로 간격이 1이 될 때까지 줄여나갑니다.
3. 동작 예시 (구체적인 설명)
정렬할 배열: [35, 33, 42, 10, 14, 19, 27, 44], 배열크기(n) = 8
첫 번째 간격(gap = 4): (초기 gap = n/2)
- 0번째 요소와 4번째 요소를 비교하고 삽입 정렬:
- 비교: 35와 14 → 교환: [14, 33, 42, 10, 35, 19, 27, 44]
- 1번째와 5번째 요소를 비교:
- 비교: 33와 19 → 교환: [14, 19, 42, 10, 35, 33, 27, 44]
- 2번째와 6번째 요소를 비교:
- 비교: 42와 27 → 교환: [14, 19, 27, 10, 35, 33, 42, 44]
- 3번째와 7번째 요소를 비교:
- 비교: 10와 44 (교환 없음)
- 결과: [14, 19, 27, 10, 35, 33, 42, 44]
두 번째 간격(gap = 2):
- 0번째와 2번째 요소를 비교:
- 비교: 14와 27 (교환 없음)
- 1번째와 3번째 요소를 비교:
- 비교: 19와 10 → 교환: [14, 10, 27, 19, 35, 33, 42, 44]
- 2번째와 4번째 요소를 비교:
- 비교: 27와 35 (교환 없음)
- 3번째와 5번째 요소를 비교:
- 비교: 19와 33 (교환 없음)
- 4번째와 6번째 요소를 비교:
- 비교: 35와 42 (교환 없음)
- 5번째와 7번째 요소를 비교:
- 비교: 33와 44 (교환 없음)
- 결과: [14, 10, 27, 19, 35, 33, 42, 44]
마지막 간격(gap = 1):
- 삽입 정렬을 수행하며 최종 정렬:
- 1번째 요소: 14와 10 → 교환: [10, 14, 27, 19, 35, 33, 42, 44]
- 2번째 요소: 14, 27 (교환 없음)
- 3번째 요소: 27와 19 → 교환: [10, 14, 19, 27, 35, 33, 42, 44]
- 4번째 요소: 27,35 (교환 없음)
- 5번째 요소: 35와 33 → 교환: [10, 14, 19, 27, 33, 35, 42, 44]
- 6번째 요소: 35, 42 (교환 없음)
- 7번째 요소: 42, 44 (교환 없음)
최종 결과: [10, 14, 19, 27, 33, 35, 42, 44]
4. 선택 정렬과의 비교
- 성능 차이:
- 선택 정렬은 항상 O(n²)의 시간 복잡도를 가지지만, 쉘 정렬은 간격을 줄여가며 효율적으로 정렬하므로 평균 시간 복잡도가 O(n^(3/2))로 더 빠릅니다.
- 교환 횟수:
- 선택 정렬은 매번 최소값을 찾기 위해 배열을 반복 스캔하며 많은 교환이 발생합니다.
- 쉘 정렬은 초기에 큰 간격을 이용해 멀리 떨어진 요소들을 정렬해, 후반부 삽입 정렬 과정에서 교환 횟수를 줄입니다.
- 실제 성능:
- 데이터가 많거나 거의 정렬된 경우 쉘 정렬이 훨씬 효율적입니다.
5. 시간 복잡도
- 평균 시간 복잡도: O(n^(3/2)) (간격 선택에 따라 다름)
- 최악 시간 복잡도: O(n²)
- 공간 복잡도: O(1) (추가 메모리를 거의 사용하지 않음)
6. 코드 예제
C 코드
#include <stdio.h>
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main() {
int arr[] = {35, 33, 42, 10, 14, 19, 27, 44};
int n = sizeof(arr) / sizeof(arr[0]);
shellSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Java 코드
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {35, 33, 42, 10, 14, 19, 27, 44};
shellSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
Python 코드
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
arr = [35, 33, 42, 10, 14, 19, 27, 44]
print(shell_sort(arr))7. 주의점
- 간격의 선택이 성능에 큰 영향을 미칩니다. 일반적으로 n/2부터 시작해 1까지 감소시키는 방식이 사용됩니다.
- 데이터가 거의 정렬되어 있을수록 효율이 높습니다.
- 삽입 정렬을 기반으로 하기 때문에 데이터 교환이 빈번히 발생합니다.
8. 장단점
장점
- 삽입 정렬보다 빠르고 간단합니다.
- 추가 메모리 사용이 적어 공간 효율적입니다.
단점
- 간격 선택 방식에 따라 성능이 크게 달라질 수 있습니다.
- 정렬 알고리즘 중 상대적으로 덜 최적화되어 있습니다.
함께 보면 좋은 글
코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.
2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준
정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주
정렬 알고리즘은 데이터를 특정 순서(오름차순, 내림차순)로 배치하는 데 사용됩니다. 코딩테스트에서 데이터를 정렬하는 문제는 매우 자주 나옵니다. 그래서 문제를 잘 분석하고, 데이터 크기
best-coding.tistory.com
댓글