Sorting
4. Shell Sort
개념
- Donald L.Shell에 의해서 제시되었으며
Insertion Sort가 부분적으로 정렬된 배열에서 매우 빠르다는 점에서 착안 (↔완전히 정렬되어 있지 않은 배열에서는 매우 느림)
Insertion Sort의 단점은 인접한 곳으로 삽입되는 경우가 아닌, 먼 곳에 삽입될 경우 많은 요소들의 이동이 발생한다는 점Insertion Sort와 달리 한 번에 정렬을 실시하지 않고 gap 값에 따라 Sublist를 구성- 단계마다
gap 값은 줄어들고 Sublist의 크기는 커짐
(일반적으로 gap은 처음에는 n/2로 시작해서 단계마다 절반이 됨)
- 마지막 단계에서
gap은 1 (하나의 Sublist만 남은 상태)
- 배열은 작은 단위로 나누고
Insertion Sort를 실시, 이후 부분적으로 정렬된 더 큰 Sublist를 다시 Insertion Sort, 해당 과정을 반복함으로 부분적으로 정렬된 곳에서 빠른 Insertion Sort의 장점을 활용
구현
static void sortIncInsertion (int list[], int first, int last, int gap)
{
int i, j, key;
for( i=first+gap ; i<=last ; i=i+gap){
key = list[i];
for( j=i-gap ; j>=first && key<list[j] ; j=j-gap )
list[j+gap]=list[j];
list[j+gap]=key;
}
}
void shellSort ( int list[], int n )
{
for( int gap=n/2; gap>0; gap = gap/2 ) {
printArray( list, n, "Shell...." );
if( (gap%2) == 0 ) gap++;
for( int i=0 ; i<gap ; i++ )
sortIncInsertion( list, i, n-1, gap );
}
}
gap만큼 서로 떨어진 요소들을 모아 Sublist 구성
(gap이 5라면, 0번과 5번 요소가 하나의 Sublist)- 배열내에 많은 요소를 이동시키는 것을 최소화
- 주어진 데이터의 특성에 따라
gap을 설정해야하며 gap에 따라 효율성이 달라짐
- 최악의 경우에는
O(n^2), 그러나 일반적으로는 O(n^1.3~1.5)
정리
Insertion Sort의 장점만 극대화- 기본적인
Insertion Sort 비교와 이동 횟수 모두를 줄임
- Unstable & Internal Sort (매우 적은 일부 메모리를 추가적으로 요구함)
- 앞선 Insertion, Selection, Bubble Sort보다 효율적
5. Merge Sort
개념
- 주어진 배열을 같은 크기의 두
Sublist로 나누고, Sublist들을 각각 정렬한 후, 다시 합침
- divide and conquer 전략을 활용: 문제를 보다 작은 단위로 나누고 각각을 해결한 뒤 합치는 방법
예시
4 2 3 1 6 5
- Divide :
4 2 3, 1 6 5 - 2개의 Sublist로 나눔
- Conquer :
2 3 4, 1 5 6 - 각각을 정렬
- Combine :
1 2 3 4 5 6 - 다시 합쳐 하나의 배열로 만듦
구현
static void Merge(int list[], int left, int mid, int right)
{
int i, j, k = left;
static int sorted[MAX_SIZE];
for( i=left, j=mid+1 ; i<=mid && j<=right ; )
sorted[k++] = (list[i]<=list[j])
? list[i++]
: list[j++];
if( i > mid )
for( int l=j ; l<=right ; l++, k++ )
sorted[k] = list[l];
else
for( int l=i ; l<=mid ; l++, k++ )
sorted[k] = list[l];
for( int l=left ; l<=right ; l++ )
list[l] = sorted[l];
}
void mergeSort ( int list[], int left, int right )
{
if( left<right ) {
int mid = (left+right)/2;
mergeSort(list, left, mid);
mergeSort(list, mid+1, right);
Merge(list, left, mid, right);
}
}
- 크기가 1인 배열이 될 때까지 나누고 합칠 때는 양쪽의 크기를 비교하며 합침
- 재귀 호출을 통해 배열을 나누고 정렬을 실시하므로 배열의 크기
n이 2의 몇번째 지수인지에 따라 깊이가 결정되므로 log₂n의 재귀 함수 호출이 발생
- 배열을 나누는 과정에서는 비교 연산이 없지만 이후 합치는 과정에서 비교 연산이 발생
- 재귀 레벨마다
n회의 비교가 발생해 전체 연산은 n * log₂n
- 합치는 과정에서 임시 배열에 값이 복사되었다가 다시 반환되는데 이 과정에서 2회 이동이 발생하므로
2n * log₂n이 됨. 따라서 시간 복잡도는 O(n * log₂n)
정리
- Divide & Conquer 전략을 기반으로 함
- 반복적으로 배열을 반으로 나누는 재귀 호출과 이를 정렬하며 합치는 과정으로 구성
- Stable & External Sort
6. Quick Sort
개념
- 평균적으로 가장 빠른 알고리즘
- Merge Sort와 마찬가지로 Divide & Conquer 전략을 사용
- 배열은 완전히 반으로 나누는 Merge Sort와 달리 불균형하게 배열을 나누기도 함
작동 방식
Pivot을 배열에서 하나 선택함Pivot보다 작은 값을 Pivot을 기준으로 왼쪽, 큰 값은 오른쪽으로 이동Pivot을 기준으로 배열이 2개의 영역으로 나뉘게 됨- 해당 과정을 재귀적으로 반복
구현
static int partition( int list[], int left, int right )
{
int low = left;
int high = right+1;
int pivot = list[left]; // pivot value
do {
do {
low++;
} while(low<=right &&list[low]<pivot);
do {
high--;
} while(high>=left && list[high]>pivot);
if( low<high ) // do until low meets high
swap(list[low], list[high]); // swap two elements
} while(low<high);
swap( list[left], list[high] ); // put pivot into proper place
return high;
}
// quick sort function: sorts list[left..right] in place ascending order
void quickSort (int list[], int left, int right)
{
if( left<right ){
int q=partition(list, left, right);
quickSort (list, left, q-1);
quickSort (list, q+1, right);
}
}
- 배열을 반씩 나누기 때문에 해당 작업은
log₂n만큼 발생
- 비교 연산 또한 매 단계마다
n회 발생
- 값의 이동은 비교 연산에 비해 극히 작아 무시할 수 있음
Pivot을 처음에 잘못 설정해 지나치게 불균형한 구조가 만들어질 경우에 가장 비효율적, 이 경우 나누는 작업이 n회 발생- 이를 방지하기 위해 하나의 요소로
Pivot을 설정하는 것보다 여러 요소의 평균이나 중간값을 사용할 수 있으며 평균적인 시간 복잡도는 θ(n * log₂n)
정리
- Divide & Conquer에 근거한 매우 효과적인 정렬
Pivot을 설정하고 이를 기준으로 배열을 나누는 방법을 사용- 가장 빠른 Internal 정렬 방식이나 Unstable 함
- Merge Sort보다 일반적으로 빠르고 메모리 공간도 적게 사용함
Pivot 선정 전략에 따라 효율성이 달라질 수 있음
