shell sort c++

#include <iostream>
#include <cstdlib>
#include <ctime>
#define MAX 30
#define MAX1 100000
#define MAX2 500000
#define MAX3 1000000
#define MAX4 5000000
#define MAX5 10000000
using namespace std;
void shell_sort3h1(int a[], int n)
{   /* h = 3*h + 1 이용 */
    int i, j, k, h, v;
    for (h = 1; h < n; h = 3 * h + 1); /* n 보다 작은 h 의 최대값 가짐 */
    for (; h > 0; h /= 3)// h의 값을 줄여가면서 계산 
    {
        for (i = h; i <= n; i++) // 최대값 h가 n보다 작을 때까지 부분 배열
        {
            v = a[i];// v에 a[i]값 저장
            j = i; // j는 인덱스를 기억 
            while(j >= h && a[j - h] > v) {
                a[j] = a[j-h];
                j = j - h;
            }
            a[j] = v;
        }
    }
}
void shell_sort3h(int a[], int n)
{   /* h = 3*h + 1 이용 */
    int i, j, k, h, v;
    for (h = 1; h < n; h = 3 * h); /* n 보다 작은 h 의 최대값 가짐 */
    for (; h > 0; h /= 3)// h의 값을 줄여가면서 계산 
    {
        for (i = h; i <= n; i++) // 최대값 h가 n보다 작을 때까지 부분 배열
        {
            v = a[i];// v에 a[i]값 저장
            j = i; // j는 인덱스를 기억 
            while(j >= h && a[j - h] > v) {
                a[j] = a[j-h];
                j = j - h;
            }
            a[j] = v;
        }
    }
}
void shell_sort5h1(int a[], int n)
{   /* h = 3*h + 1 이용 */
    int i, j, k, h, v;
    for (h = 1; h < n; h = 5 * h + 1); /* n 보다 작은 h 의 최대값 가짐 */
    for (; h > 0; h /= 5)// h의 값을 줄여가면서 계산 
    {
        for (i = h; i <= n; i++) // 최대값 h가 n보다 작을 때까지 부분 배열
        {
            v = a[i];// v에 a[i]값 저장
            j = i; // j는 인덱스를 기억 
            while(j >= h && a[j - h] > v) {
                a[j] = a[j-h];
                j = j - h;
            }
            a[j] = v;
        }
    }
}
void checkSort(int a[], int n){
    int i, sorted;
    sorted = 1;
    for( i = 0; i < n; i ++) {
        if(a[i] > a[i + 1]) {
            sorted = 0;
        }
        if(!sorted) {
            break;
        }
    }
    if(sorted == 0) {
        cout << "sort error" << endl;
    }
    else {
        cout << "sort complete" << endl;
    }
}
int main()
{
	int n1 = MAX1;
    int n2 = MAX2;
    int n3 = MAX3;
    int n4 = MAX4;
    int n5 = MAX5;

	int arr[n3];
	clock_t start, finish, start1, finish1;
    double duration, duration1;

	for(int i = 0; i < n3; i++) {
		arr[i] = rand() % n3;
	}
    start = clock();
    
    shell_sort5h1(arr, n3);
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "increament : 5h + 1, decreament h/5 shell sort time(N = " << n3 << ") : " << duration <<"sec";
    cout << '\n';
    checkSort(arr, n3);
    return 0;
}

전체 코드이다. shell sort는 한 배열을 여러 개의 부분 배열로 나누어 그 배열에 대해 insert sort 를 실행하는 정렬방법이다. 

이 때 shell sort의 알고리즘을 살펴보면 다음과 같다.

---

1. shell sort 

void shell_sort3h1(int a[], int n)
{   /* h = 3*h + 1 이용 */
    int i, j, k, h, v;
    for (h = 1; h < n; h = 3 * h + 1); /* n 보다 작은 h 의 최대값 가짐 */
    for (; h > 0; h /= 3)// h의 값을 줄여가면서 계산 
    {
        for (i = h; i <= n; i++) // 최대값 h가 n보다 작을 때까지 부분 배열
        {
            v = a[i];// v에 a[i]값 저장
            j = i; // j는 인덱스를 기억 
            while(j >= h && a[j - h] > v) {
                a[j] = a[j-h];
                j = j - h;
            }
            a[j] = v;
        }
    }
}

h를 통해 전체 array개수보다는 작으면서 1부터 시작해 일정한 간격으로 index를 이동했을 때 가장 큰 h를 잡는다. 

그 후 h를 h/3으로 줄여가면서 부분 배열에 대해 insertion sort를 수행하면 된다. 

 

나는 shell sort의 데이터의 수에 따라 또한 증감식에 따라 시간을 측정해보았다. 

1.     증가식 3h + 1, 감소식 h/3의 경우 n = 100000, 500000의 경우

N = 5000000의 경우이다.

N = 10000000

2.     증가식 3h ,  감소식 h/3의 경우

N = 100000, 500000의 경우

N = 1000000의 경우

N = 5000000의 경우

N = 10000000의 경우

1.     증가식 5h+1, 감소식 h/5의 경우

N = 100000, 500000일 경우

N = 1000000

N = 5000000

N = 10000000

구현을 하고 시간을 측정해본 결과 증가식이 3h + 1인 경우에 가장 빠른 시간이 측정되었다. 수학적으로 증명은 하지 못하겠으나 구글링을 통해 본 결과에서도 3h+1이 가장 보편적으로 사용되는 증가식이라고 한다.