[06. 정렬 알고리즘] 쉘 정렬(Shell Sort)

#include <iostream>
using namespace std;

bool is_sorted(int arr[], int N) {
    for (int i = 1; i < N; i++)
        if (arr[i - 1] > arr[i])
            return false;
    return true;
}

• 기본 쉘 정렬

void ShellSort1(int arr[], const int N) {
    for (int gap = N >> 1; gap > 0; gap >>= 1) {
        for (int first = 0; first < gap; first++)
            // Insertion sort
            for (int i = first + gap; i < N; i += gap) {
                int key = arr[i];
                int j = i - gap;
                for (; j >= first && arr[j] > key; j -= gap)
                    arr[j + gap] = arr[j];

                arr[j + gap] = key;
            }
    }
}

• 코드 가독성 (for문 한개 줄임)

void ShellSort2(int arr[], const int N) {
    for (int gap = N >> 1; gap > 0; gap >>= 1) {
        for (int i = gap; i < N; i++) {
            int key = arr[i];
            int j = i - gap;
            for (; j >= 0 && arr[j] > key; j -= gap)
                arr[j + gap] = arr[j];

            arr[j + gap] = key;
        }
    }
}

• gap = 3n+1꼴 (Group끼리 섞임)

void ShellSort3(int arr[], const int N) {
    int gap = 1;
    while (gap < N) gap = 3 * gap + 1;
    for (gap /= 3; gap > 0; gap /= 3) {
        for (int i = gap; i < N; i++) {
            int key = arr[i];
            int j = i - gap;
            for (; j >= 0 && arr[j] > key; j -= gap)
                arr[j + gap] = arr[j];

            arr[j + gap] = key;
        }
    }
}

int main(int num) {
    const int N = RAND_MAX;
    int arr[N];

    const int ntimes = 200;
    int total = 0;
    for (int j = 0; j < ntimes; j++) {
        for (int i = 0; i < N; ++i)
            arr[i] = rand();

        int start = clock();
        //ShellSort1(arr, N);					// 5~6 ms
        //ShellSort2(arr, N);					// 5~6 ms
        ShellSort3(arr, N);						// 4~5 ms

        total += clock() - start;
    }
    cout << total / ntimes << endl;
    cout << is_sorted(arr, N) << endl;
}

이동 횟수 비교

#include <iostream>
using namespace std;

int move_count = 0;

void InsertionSort(int arr[], const int N) {
    for (int i = 1; i < N; i++) {
        int key = arr[i];

        int j = i - 1;
        for (; j >= 0 && arr[j] > key; --j) {
            arr[j + 1] = arr[j];
            move_count++;
        }

        arr[j + 1] = key;
        move_count += 2;
    }
}

void ShellSort2(int arr[], const int N) {
    for (int gap = N >> 1; gap > 0; gap >>= 1) {
    	//gap |= 1;   						// 이동횟수 변화 없음(지워도 됨)
        for (int i = gap; i < N; i++) {
            int key = arr[i];							// 이동
            int j = i - gap;
            for (; j >= 0 && arr[j] > key; j -= gap) {
                arr[j + gap] = arr[j];					// 이동
                move_count++;
            }

            arr[j + gap] = key;							// 이동
            move_count += 2;
        }
    }
}

void ShellSort3(int arr[], const int N) {
    int gap = 1;
    while (gap < N) gap = 3 * gap + 1;
    for (gap /= 3; gap > 0; gap /= 3) {
        for (int i = gap; i < N; i++) {
            int key = arr[i];
            int j = i - gap;
            for (; j >= 0 && arr[j] > key; j -= gap)
                arr[j + gap] = arr[j];

            arr[j + gap] = key;
        }
    }
}

int main(int num) {
    const int N = RAND_MAX;
    int arr[N];

    for (int i = 0; i < N; ++i)
        arr[i] = rand();
	
    //InsertionSort(arr, N);	// 268666951
    //ShellSort2(arr, N);		// 1468455
	ShellSort3(arr, N);			// 1264446

	cout << move_count << endl;
}

• 삽입정렬에 비해 쉘정렬은 이동횟수가 급격히 줄어든다.
• gap = 3n+1 꼴일때 최대 효율