정렬 알고리즘에서 소개된 각 알고리즘의 예제를 작성하는 문서입니다. 모든 알고리즘은 int형을 오름차순으로 정렬하도록 작성합니다. 현재 모든 예제는 C++를 기준으로 작성됐습니다.
1 선택 정렬
#include <algorithm>
using namespace std;
void selection(int *array, int begin, int end)
{
for(int i = begin; i < end; ++i)
{
for(int j = i + 1; j <= end; ++j)
{
if(array[i] > array[j])
{
swap(array[i], array[j]);
}
}
}
}
2 거품 정렬
#include <algorithm>
using namespace std;
void bubble(int *array, int begin, int end)
{
for(int i = end; i > begin; --i)
{
for(int j = begin; j < i; ++j)
{
if(array[j] > array[j + 1])
{
swap(array[j], array[j + 1]);
}
}
}
}
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);
}
}
4 카운팅 정렬
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];
}
}
5 힙 정렬
#include <algorithm>
using namespace std;
void heap_construct(int *array, int index)
{
while(index > 1)
{
if(array[index] >= array[index / 2]) {
break;
}
swap(array[index], array[index / 2]);
index /= 2;
}
}
void heap_setting(int *array, int index, int heap_size)
{
int revision;
int temp;
int pivot;
while(heap_size >= index * 2)
{
if(index * 2 + 1 > heap_size && array[index * 2] < array[index])
{
swap(array[index * 2], array[index]);
index *= 2;
continue;
}
else if(index * 2 + 1 > heap_size)
{
break;
}
revision = array[index * 2] < array[index * 2 + 1] ? 0 : 1;
temp = array[index * 2 + revision];
pivot = index * 2 + revision;
if(temp >= array[index])
{
break;
}
swap(array[index], array[pivot]);
}
}
void heap(int *array, int begin, int end) {
int heap_tree[100002];
int heap_size = 0;
for(int i = begin; i <= end; ++i)
{
heap_tree[++heap_size] = array[i];
heap_construct(heap_tree, heap_size);
}
for(int i = begin; i<end; ++i)
{
array[i] = heap_tree[1];
heap_tree[1] = heap_tree[--heap_size];
heap_setting(heap_tree, 1, heap_size);
}
}
6 기수 정렬
#include <vector>
using namespace std;
void radix(int *array, int begin, int end)
{
pair<int, int> temp;
vector<pair<int, int>> radix_array[2][10];
int pivot = 0;
for(int i = 0; i < n; ++i) {
temp = make_pair(array[i], array[i]);
radix_array[pivot][temp.second % 10].push_back(temp);
}
while(radix_array[pivot][0].size() != end - begin + 1)
{
if(pivot)
{
for(int i = 9; i >= 0; --i)
{
while(radix_array[pivot][i].size())
{
temp = radix_array[pivot][i].back();
radix_array[pivot][i].pop_back();
temp = make_pair(temp.first, temp.second / 10);
radix_array[!pivot][temp.second % 10].push_back(temp);
}
}
}
else
{
for(int i = 0; i < 10; ++i)
{
while(radix_array[pivot][i].size())
{
temp = radix_array[pivot][i].back();
radix_array[pivot][i].pop_back();
temp = make_pair(temp.first, temp.second / 10);
radix_array[!pivot][temp.second % 10].push_back(temp);
}
}
}
pivot = pivot ? 0 : 1;
}
int d = pivot ? end : begin;
while(radix_array[pivot][0].size())
{
if(pivot)
{
o[--d] = radix_array[pivot][0].back().first;
}
else
{
o[++d] = radix_array[pivot][0].back().first;
}
radix_array[pivot][0].pop_back();
}
}
7 병합 정렬
void merge(int *array, int begin, int end)
{
int left_pivot = (begin + end) / 2;
int right_pivot = left_pivot + 1;
if(begin != left_pivot)
{
merge(array, begin, left_pivot);
merge(array, right_pivot, end);
}
int temp[end - begin + 1];
int first_division = begin;
int second_division = right_pivot;
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(int i = begin; i <= end; ++i)
{
array[i] = temp[i - begin];
}
}