정렬 시간 비교 (버블, 선택, 삽입, 쉘, 힙, 퀵)

#include <iostream>
#include <algorithm>
#include <random>
#include <queue>
using namespace std;

// BubbleSort:		std::swap() 함수보다 훨씬(2배 이상) 빠르다.
// SelectionSort:	차이를 느끼기 어렵다.
// QuickSort:		큰 속도 개선(6ms --> 4ms)이 있었다.
#define swap2(type, x, y) do { type t = x; x = y; y = t; } while (false)

void BubbleSort(int arr[], const int N) {
    for (int i = N; i > 1; i--)
        for (int j = 1; j < i; j++)
            if (arr[j - 1] > arr[j])
                swap2(int, arr[j - 1], arr[j]);
}

// 단순 선택 정렬(straight selection sort)
void SelectionSort(int arr[], const int N) {
    for (int i = 0; i < N - 1; i++) {
        int idx = i;
        for (int j = i + 1; j < N; j++)
            if (arr[idx] > arr[j])
                idx = j;

        swap2(int, arr[i], arr[idx]);
    }
}

// 단순 삽입 정렬(straight insertion sort) / 셔틀 정렬(shuttle sort)
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];

        arr[j + 1] = key;
    }
}

void ShellSort(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;
        }
    }
}

static void partition(int arr[], const int left, const int right) {
	if (left >= right)
		return;

	int pl = left;
	int pr = right;
	int x = arr[(pl + pr) / 2];
	while (true) {
		while (arr[pl] < x) pl++;
		while (arr[pr] > x) pr--;
		if (pl >= pr)
			break;

        swap2(int, arr[pl], arr[pr]);
		pl++, pr--;
	}
	if (pl == pr)
		pl++, pr--;

	partition(arr, left, pr);
	partition(arr, pl, right);
}

void QuickSort(int arr[], const int N) {
	partition(arr, 0, N - 1);
}

static int* buf;

static void __mergesort(int arr[], const int N) {
    if (N <= 1) return;

    const int half_N = (N >> 1) + (N & 1);
    __mergesort(arr, half_N);
    __mergesort(arr + half_N, N >> 1);

    for (int i = 0; i < half_N; i++)
        buf[i] = arr[i];

    int i = 0;
    int j = half_N;
    int k = 0;
    while (i < half_N && j < N)
        // < 가 아닌 <= 를 사용한다. (stable sort)
        arr[k++] = (buf[i] <= arr[j]) ? buf[i++] : arr[j++];
    while (i < half_N)
        arr[k++] = buf[i++];
}

void MergeSort(int arr[], const int N) {
    const int half_N = (N >> 1) + (N & 1);
    buf = new int[half_N];
    __mergesort(arr, N);
    delete[] buf;
}

static void heapify(int arr[], int parent, const int last) {
    int temp = arr[parent];
    while (parent < (last + 1) / 2) {
        int lchild = parent * 2 + 1;
        int rchild = lchild + 1;
        int child = (lchild == last || arr[lchild] > arr[rchild]) ? lchild : rchild;
        if (temp >= arr[child])
            break;
        arr[parent] = arr[child];
        parent = child;
    }
    arr[parent] = temp;
}

void HeapSort(int arr[], const int N) {
    if (N <= 1) return;
    
    const int last = N - 1;
    for (int parent = (last-1) / 2; parent >= 0; parent--)
        heapify(arr, parent, N - 1);
    swap2(int, arr[0], arr[N - 1]);
    
    for (int last = N - 2; last > 0; last--) {
        heapify(arr, 0, last);
        swap2(int, arr[0], arr[last]);
    }
}

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

int main() {
    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();
        //BubbleSort(arr, N);					// 1933 ms	(ntimes = 3)
        //SelectionSort(arr, N);                // 576 ms	(ntimes = 5)
        //InsertionSort(arr, N);                // 551 ms	(ntimes = 5)
        //ShellSort(arr, N);                    // 4~5 ms	(ntimes = 200)
        //QuickSort(arr, N);                    // 3 ms		(ntimes = 200)
        //MergeSort(arr, N)                     // 4 ms		(ntimes = 200)
        HeapSort(arr, N);						// 3~4 ms	(ntimes = 200)
        total += clock() - start;
    }
    cout << total / ntimes << endl;
    cout << is_sorted(arr, N) << endl;
}

더 자세히

버블 정렬 [새창 열기]

삽입 정렬 [새창 열기]

쉘 정렬 [새창 열기]

퀵 정렬 [새창 열기]

힙 정렬 [새창 열기]

도수 정렬 [새창 열기]