h(k)를 큰 수로 놓아서 순서가 맞지 않는 키들을 장거리 이동시킴으로써 일반 삽입정렬보다 빨리 제자리에 접근시키도록 하는 정렬
입력 배열을 부분배열로 나누너 정렬하는 과정을 여러번 걷침
부분배열의 크기와 개수를 변화시켜 가면서 과정을 진행
부분배열의 개수를 정하기 위해 양수로 이루어진 임의의 순열 h(k), h(k-1), ....h1 을 선택
이 순열에서 1<i<k 인 i 에 대하여 h(i-1) < h(i) < h(i=1) 이 항상 만족되도록 함
또한 임의의 i와 j에 대하여 i<j 이면 h(j)가 h(i)의 배수가 되지 않도록 한다
항상 h1=1이 되도록 한다.
첫째 단계에서 전체배열을 h(k) 개의 부분배열로 나누어 각 부분배열에 삽입 정렬을 적용
두 번째 단게에서 전체배열을 h(k-1) 개의 부분배열로 나누어 각 부분배열에 삽입 정렬 적용
이 과정을 계속하다가 마지막 단계에서는 h1개의 부분배열에서 삽입정렬을 적용시켜 정렬을 끝냄
쉡 정렬 예제
void ShellSort(vector<int> &array)
{
int h, i, j, value;
int n = array.size();
h = 1;
//부분배열 개수 결정
do h = 3 * h + 1; while (h < n);
do {
h /= 3;
//삽입정렬
for (i = h; i < n; i++)
{
value = array[i];
j = i;
while (array[j - h] > value) {
array[j] = array[j - h];
j -= h;
if (j <= h - 1) break;
}
array[j] = value;
}
} while (h > 1);
}
정렬할 키들을 배열 내에서 적당히 이동시키면서 두 조건이 만족되도록 배열을 오른쪽 부분 배열과 왼쪽 부분배열로 나눈다.
(1) 왼쪽 부분배열에 있는 모든 키들은 오른쪽 부분배열의 가장 작은 키보다 작다.
(2) 오른쪽 부분배열에 있는 모든 키들은 왼쪽 부분배열의 가장 큰 키보다 크다.
배열을 이렇게 나누면, 앞으로의 정렬 과정에서 왼쪽 부분배열의 키들과 오른쪽 부분배열의 키들이 전혀 섞이지 않게 된다.
이 점을 이용하여 왼쪽 부분배열과 오른쪽 부분배열에 독립적으로 퀵 정렬을 순환적으로 적용함으로써 배열 전체를 정렬할 수 있다.
정렬할 배열을 두 개의 부분배열로 나누는 방법
배열에서 임의의 키를 선택하여 이를 분할 원소라 한다.
분할하고자 하는 배열을 양끝으로부터 배열의 중심을 향하여 동시에 검색하여 간다.
왼쪽에서 오른쪽 방향으로 검색할 때는 분할 원소보다 큰 키를 찾는다.
오른쪽으로부터 왼쪽을 향하여 검색할 때는 분할 원소보다 작은 키를 찾는다.
이 두 키의 자리를 서로 바꾸고 검색을 계속한다.
검색 과정에서 이와 같은 조건을 만족하는 키들이 또 나타날 때마다 이들의 자리를 서로 바꾼다.
양끝에서 중심을 향하여 진행하던 검색이 배열의 어느 곳에서 서로 만나게 되면 검색을 끝내고 그 자리에 분할 원소를 넣는다.
이렇게 되면 분할 원소는 제자리를 찾는다.
분할 원소의 왼쪽에 있는 모든 키들은 분할 원소보다 작고, 오른쪽에 있는 모든 키들은 분할 원소보다 크다는 조건을 만족한다.
퀵정렬 예시
시간복잡도
Worst Case
ex> 분할 원소 하나만 제자리를 잡고 나머지 원소 모두가 왼쪽 혹은 오른쪽 부분 배열로 되는 경우
-> 1, 2, 3, 4, 5, 6, 7, 8, 9 (이미 제 순서로 된 경우)
-> 9, 8, 7, 6, 5, 4, 3, 2, 1 (역순으로 된 경우)
n+(n−1)+(n−2)+...+1=O(n2)
Best Case
ex> 분할 원소를 중심으로 두 부분 배열이 정확히 둘로 나뉘는 경우
2T(n/2) +n
=4T(n/4) + 2(n/2) + n
=8T(n/8)+n+n+n
=....
=n+nlgn
=O(nlogn)
Average Case
O(nlogn)
Partition 함수
int Partition(int A[], int left, int right)
{
int partElem, value, temp;
partElem = left;
value = A[partElem];
//left와 right가 교차할 때까지 반복
do {
//A[left]가 분할원소값보다 작으면 left를 반복증가시킴
do { } while (A[++left] < value);
//A[right]가 분할원소값보다 크면 right를 반복감소시킴
do { } while (A[--right] > value);
//두 값을 교환
if (left < right) swap(A[left], A[right]);
else break;
} while (left<right);
//분할원소의 자리를 찾아줌
A[partElem] = A[right];
A[right] = value;
return right;
}
QuickSort함수
void QuickSort(int A[], int left, int right)
{
if (right > left)
{
int middle = Partition(A, left, right + 1);
//분할원소를 기준으로 왼쪽에서 재정렬
QuickSort(A, left, middle - 1);
//분할원소를 기준으로 오른쪽에서 재정렬
QuickSort(A, middle + 1, right);
}
}
삽입 정렬의 i번째 단계가 시작될 때에 배열의 맨 처음 i-1개의 키인 A[0:i-2]는 이미 정렬되어 있다
여기에 A[i-1]를 삽입하여 A[0:i-1]이 정렬되도록 하는 것이 i번째 단계의 목표이다
A[i-1]자리에 있던 키가 제자리를 찾을 때까지 A[i-1]보다 큰 값을 갖는 A[i-2], A[i-3], ... 등을 오른쪽으로 한 자리씩 이동시키고 원래 A[i-1]에 있던 키를 이때 생긴 빈 자리에 넣는다
이러한 과정을 n-1회 실행하면 배열이 정렬된다
시간복잡도 O(n^2)
공간복잡도 O(n)
삽입 정렬 예제
알고리즘
void InsertionSort(int A[], int n){
/* 입력 : A[0:n] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
A[0]는 A[1:n]의 어느 값보다도 더 작은 더미 키이다.
출력 : A[0:n] - A[0]은 더미 키이고, A[1:n]은 정렬된 배열임. */
int i, j, Value;
for (i=2; i<=n ; i++){
Value = A[i];
j=i;
while(A[j-1] > Value) {
A[j] = A[j-1];
j--;
}
A[j]=Value;
}
}
삽입 정렬에서는 키간의 비교 횟수가 키들의 원래 순서에 민감하게 반응한다
키가 내림차순으로 이미 정렬되어 있는 경우 가장 많은 비교를 하게 된다
삽입 정렬의 최악의 경우에 2+3+...+n = n(n+1)/2 -1 번의 비교를 필요로 한다
사용하는 메모리 공간은 배열의 첨자에 쓰이는 변수와 삽일할 키의 값을 잠시 기억하는데 사용하는 변수뿐이므로 제자리 정렬이다
두 개의 동일한 값을 가지는 키의 상대적 위치가 정렬 후에도 변하지 않으므로 안정적인 정렬이다.
