문서:정렬 알고리즘/예제

분류

알고리즘

정렬 알고리즘에서 소개된 각 알고리즘의 예제를 작성하는 문서입니다. 모든 알고리즘은 int형을 오름차순으로 정렬하도록 작성합니다. 현재 모든 예제는 C++를 기준으로 작성됐습니다.

1. O(n²)인 것

1.1. 버블 정렬1.2. 선택 정렬1.3. 삽입 정렬

2. O( n log n )인 것

2.1. 병합 정렬2.2. 힙 정렬2.3. 퀵 정렬

3. 기타

3.1. 카운팅 정렬3.2. 기수 정렬

1. O(n²)인 것

1.1. 버블 정렬

#include <algorithm>

using namespace std;

void bubble(int *array, int begin, int end)
{
    for (int i = end; i > begin; --i)
    {
        bool isdone = true;
        int j;
        for (j = begin; j < i; ++j)
        {
            if (array[j] > array[j + 1])
            {
                isdone=false;
                swap(array[j], array[j + 1]);
            }
        }
        if(isdone == true) break;
    }
}

1.2. 선택 정렬

#include <algorithm>

using namespace std;

void selection(int *array, int begin, int end)
{
    for (int i = begin; i < end; ++i)
    {
        int imin = i;
        for (int j = i + 1; j <= end; ++j)
        {
            if (array[imin] > array[j]) imin = j;
        }
        if (imin != i) swap(array[i], array[imin]);
    }
}

1.3. 삽입 정렬

void insertion(int *array, int begin, int end)
{
	for (int i = begin + 1; i <= end; i++)
	{
		int j, v = array[i];
		for (j = i; j > begin && array[j - 1] > v; j--)
			array[j] = array[j - 1];
		if (i != j) array[j] = v;
	}
}

2. O( n log n )인 것

2.1. 병합 정렬

#include <vector>

void merge(int *array, int begin, int end)
{
    if(begin < end)
    {
        int left_pivot = (begin + end) / 2;
        int right_pivot = left_pivot + 1;

        //Divide
        if (begin != left_pivot)
        {
            merge(array, begin, left_pivot);
            merge(array, right_pivot, end);
        }

        //Conquer
        std::vector<int> temp(end - begin + 1);
        int first_division = begin;
        int second_division = right_pivot;
        int i=0;

        while (first_division <= left_pivot && second_division <= end)
        {
            if (array[first_division] <= array[second_division])
            {
                temp[i++] = array[first_division++];
            }
            else
            {
                temp[i++] = array[second_division++];
            }
        }

        if (first_division > left_pivot)
        {
            while (second_division <= end)
            {
                temp[i++] = array[second_division++];
            }
        }
        else
        {
            while (first_division <= left_pivot)
            {
                temp[i++] = array[first_division++];
            }
        }

        for (i = begin; i <= end; ++i)
        {
            array[i] = temp[i - begin];
        }
    }
}

2.2. 힙 정렬

#include <algorithm>

using namespace std;

void heapify(int *array, int index, int size)
{
	for (int ch = (index << 1) | 1; ch < size; index = ch, ch = ch << 1 | 1)
	{
		if (ch + 1 < size && array[ch + 1] > array[ch]) ++ch;
		if (array[ch] <= array[index]) return;
		swap(array[ch], array[index]);
	}
}

void heap(int *array, int begin, int end)
{
	int *base = array + begin;
	int size = end - begin + 1;
	for (int i = size / 2 - 1; i >= 0; i--)
		heapify(base, i, size);

	while (--size >= 1)
	{
		swap(base[0], base[size]);
		heapify(base, 0, size);
	}
}

2.3. 퀵 정렬

#include <algorithm>

using namespace std;

void quick(int *array, int left, int right)
{
    int pivot = left;
    int left_pivot = left;
    int right_pivot = right;
    
    while (left_pivot < right_pivot)
    {
        while (array[left_pivot] <= array[pivot] && left_pivot < right)
        {
            left_pivot += 1;
        }
        
        while (array[right_pivot] >= array[pivot] && right_pivot > left)
        {
            right_pivot -= 1;
        }
        
        if (left_pivot < right_pivot)
        {
            swap(array[left_pivot], array[right_pivot]);
            
            continue;
        }

        swap(array[pivot], array[right_pivot]);
        quick(array, left, right_pivot - 1);
        quick(array, right_pivot + 1, right);
    }
}

3. 기타

3.1. 카운팅 정렬

int count[100001];

void counting(int *array, int begin, int end) 
{
    int temp[100001];
    
    for (int i = begin; i <= end; ++i)
    {
        count[array[i]] += 1;
    }
    
    for (int i = 1; i <= 100000; ++i)
    {
        count[i] += count[i - 1];
    }

    for (int i = begin; i <= end; ++i)
    {
        temp[--count[array[i]]] = array[i];
    }

    for (int i = begin; i <= end; ++i)
    {
        array[i] = temp[i - begin];
    }
}

3.2. 기수 정렬

#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

void radix(int *array, int begin, int end)
{
    // for signed-integer to be sorted correctly
    for (int i = begin; i <= end; i++)
        array[i] ^= INT_MIN;

    vector<int> buf(end - begin + 1), cnt(256), idx(256);
    int *org = array + begin, *des = &buf[0];

    for (int i = 0; i < sizeof(int); i++, swap(org, des))
    {
        fill(cnt.begin(), cnt.end(), 0);

        for (int j = 0; j <= end - begin; j++)
            cnt[(org[j] >> (i << 3)) & 0xFF]++;

        idx[0] = 0;
        for (int i = 1; i < 256; i++)
            idx[i] = idx[i - 1] + cnt[i - 1];

        for (int j = 0; j <= end - begin; j++)
            des[idx[(org[j] >> (i << 3)) & 0xFF]++] = org[j];
    }

    for (int i = 0; i <= end - begin; i++)
        org[i] ^= INT_MIN;

    if (org != array + begin)
        copy(buf.begin(), buf.end(), array + begin);
}