쉘 정렬 (Shell Sort)
개요
쉘 정렬 (Shell Sort) 은 삽입 정렬을 개선한 버전으로, 배열을 일정 간격(gap)으로 나눈 후 부분 배열을 삽입 정렬하고, 그 간격을 점차 줄여가며 배열을 정렬하는 알고리즘임. 일반적으로 의 시간 복잡도를 가짐. (h에 따라 다르며, 불안정 정렬임)
쉘 정렬이란?
쉘 정렬은 삽입 정렬의 문제점을 개선하기 위해 고안되었다.
쉘(Shell)은 껍질 혹은 틀을 의미한다. 이런 의미를 생각했을 때, 쉘 정렬은 큰 틀을 먼저 잡고, 세부적으로 점차 정렬해 들어가는 것이 특징이라고 생각하면 된다.
삽입 정렬은 작은 데이터 집합에 대해 효율적이지만, 큰 데이터 집합에서는 성능이 떨어지는 단점이 있다. 쉘 정렬은 배열을 간격으로 나누어 그 간격 내에서 삽입 정렬을 수행하며, 간격을 줄여 나가면서 점진적으로 전체 배열을 정렬해 나가는 방식이기 때문이다.
쉘 정렬 작동 원리 설명
쉘 정렬의 핵심은 간격(gap)을 설정하고, 그 간격에 따라 배열을 부분적으로 나누어 삽입 정렬을 수행한 후, 간격을 줄여가면서 전체 배열을 점진적으로 정렬하는 것이다. 처음에는 큰 간격을 사용해 배열을 크게 나누어 처리하고, 간격을 좁혀가면서 더 작은 그룹을 정렬해 나간다.
사실 위 애니메이션만 보고는 이해가 힘들다.
예를 들어, 배열 [22, 37, 15, 19, 12]에 쉘 정렬을 적용해보자.
1.
첫 번째 단계: 간격을 3으로 설정하면 배열은 다음과 같이 나뉜다.
•
첫 번째 그룹: [22, 19] (1번 요소와 4번 요소)
•
두 번째 그룹: [37, 12] (2번 요소와 5번 요소)
•
세 번째 그룹: [15] (3번 요소)
간격이 3이므로, 1번에서 3만큼 큰 4번 요소가 한 그룹으로 묶인다.
각 그룹 내에서 삽입 정렬을 수행하면, 첫 번째 그룹 [22, 19]는 [19, 22]로, 두 번째 그룹 [37, 12]는 [12, 37]로 정렬된다. 배열 상태는 [19, 12, 15, 22, 37]이 된다.
2.
두 번째 단계: 간격을 1로 줄이면 전체 배열을 다시 한 번 삽입 정렬하는데, 이미 부분적으로 정렬된 상태에서 삽입 정렬을 수행하기 때문에 더 적은 교환으로 배열을 완전히 정렬할 수 있다. 배열 [19, 12, 15, 22, 37]에서 12를 앞으로, 15를 적절한 위치로 삽입하여 최종 배열 [12, 15, 19, 22, 37]이 완성된다.
h-정렬… 그게 뭔데?
앞서 언급한 간격을 h로 나타내는 것이다.
따라서 4-정렬이라고 한다면, 간격을 4로하여 쉘 정렬을 실행하는 알고리즘이라고 보면 된다.
그렇다면 1-정렬은 무엇일까? 바로 삽입 정렬 그 자체이다. 간격이 1이라면 모든 데이터에 대해서 삽입 정렬을 진행하는 꼴이 되는 것이다.
쉘 정렬의 시간 복잡도 계산
쉘 정렬의 시간 복잡도는 사용하는 간격의 선택에 따라 달라진다. 일반적으로 쉘 정렬의 시간 복잡도는 최선의 경우 O(n log n)에서 최악의 경우 O(n²)까지 다양하게 나타날 수 있다. 간격을 어떻게 줄여가는지에 따라 성능이 결정되며, 실제로 대부분의 경우 삽입 정렬보다 훨씬 더 효율적이다.
통계적으로 봤을 때는 보통 의 시간 복잡도를 가진다고 한다. 보통의 삽입 정렬보다는 빠르지만, 보다는 느리다.
쉘 정렬 코드 (4-정렬, C++)
#include <iostream>
using namespace std;
void printArray(int arr[], int n, int gap) {
cout << "간격 " << gap << "로 정렬 중: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void shellSort(int arr[], int n) {
// 4-정렬을 위해 초기 간격을 4로 설정
int gap = 4;
// 간격이 0보다 크면 계속 정렬
while (gap > 0) {
// 각 간격에 대해 삽입 정렬 수행
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];
}
// 적절한 위치에 temp 삽입
arr[j] = temp;
}
// 정렬 중 배열 상태 출력
printArray(arr, n, gap);
// 간격을 줄여 나감 (예: 간격 4에서 간격 1로 줄임)
gap /= 2; // 간격을 반으로 줄임 (여기서는 4 -> 2 -> 1 순으로 줄어듬)
}
}
int main() {
int arr[] = {22, 37, 15, 19, 12, 8, 9 ,25};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "정렬 전 배열: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
shellSort(arr, n);
cout << "정렬 후 배열: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
C++
복사
•
정렬 과정까지 출력을 한 결과를 봐보자.
요약
•
쉘 정렬은 배열을 간격으로 나누어 각 간격 내에서 삽입 정렬을 수행하며, 간격을 점차 줄여가며 전체 배열을 정렬하는 알고리즘이다.
•
간격 설정에 따라 성능이 달라지며, 일반적으로 삽입 정렬보다 효율적이고, 시간 복잡도는 보통 O(n√n)이다.
•
쉘 정렬은 삽입 정렬을 개선한 방식으로 큰 데이터 집합에서도 유용하다.
REFERENCES
1.
주우석, 2015, C/C++로 배우는 자료구조론, 한빛미디어
Written by Changyu Lee, 2024-10-13