1. 개요
정렬 알고리즘에서 소개된 각 알고리즘의 예제를 정리한 문서.모든 알고리즘은 int형을 오름차순으로 정렬하도록 작성되었고, 현재 모든 예제는 Python과 C++를 기준으로 작성되었다.
2. O(n²)인 것
2.1. 버블 정렬
#!syntax cpp
#include <algorithm>
//C++
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;
}
}
#!syntax python
#python
def bubble(lst):
for i in range(len(lst), 0, -1):
flag = True
for j in range(1, i):
if lst[j - 1] > lst[j]:
lst[j - 1], lst[j], flag = lst[j], lst[j - 1], False
if flag: break
return lst
2.1.1. 칵테일 정렬
#!syntax cpp
#include <algorithm>
//C++
using namespace std;
void cocktail(int *array, int begin, int end)
{
bool isdone = true;
do
{
isdone = true;
for (int i = begin; i < end; ++i)
{
if (array[i] > array[i + 1])
{
isdone = false;
swap(array[i], array[i + 1]);
}
}
--end; // 가장 큰 수가 판별되었다.
if (isdone == true) break;
isdone = true;
for (int i = end - 1; i >= begin; --i)
{
if (array[i] > array[i + 1])
{
isdone = false;
swap(array[i], array[i + 1]);
}
}
++begin; //가장 작은 수가 판별되었다.
} while(isdone == false);
}
2.2. 선택 정렬
#!syntax cpp
//C++
#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;
}
swap(array[i], array[imin]);
}
}
#!syntax python
#python
def selection(lst):
for i in range(len(lst) - 1):
min_idx, min_val = i, lst[i]
for j, v in enumerate(lst[i + 1:],i + 1):
if v < min_val:
min_idx, min_val = j, v
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
2.3. 삽입 정렬
#!syntax cpp
//C++
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;
}
}
#!syntax python
#python
def insertion(lst):
for i, v in enumerate(lst[1:], 1):
while i > 0 and lst[i - 1] > v:
lst[i] = lst[i - 1]
i -= 1
lst[i] = v
return lst
2.3.1. 이진 삽입 정렬
#!syntax cpp
//C++
void binary_insertion(int *array, int begin, int end)
{
for (int i = begin + 1; i <= end; i++)
{
int v = array[i], first = begin, last = i - 1;
while (first <= last)
{
int mid = (first + last) / 2;
if (array[m] > v)
last = mid - 1;
else
first = mid + 1;
}
// 이진 탐색 후 first - 1(last)까지는 항상 v 보다 작거나 같다.
for (int j = i; j > first; j--)
array[j] = array[j - 1];
array[first] = v;
}
}
#!syntax python
#python
def binary_insertion(lst):
for i, v in enumerate(lst[1:], 1):
first, last = 0, i
while first < last:
mid = (first + last) // 2
if lst[mid] > v:
last = mid
else:
first = mid + 1
# 이진 탐색 후 first - 1(last)까지는 항상 v 보다 작거나 같다.
for j in range(i, first, -1):
lst[j] = lst[j - 1]
lst[first] = v
return lst
3. O( n log n )인 것
3.1. 병합 정렬
#!syntax cpp
#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];
}
}
}
#!syntax python
#python
def merge(lst):
mid = len(lst) // 2
# Divide
left, right = lst[:mid], lst[mid:]
lst[:] = []
l_len, r_len = len(left), len(right)
if l_len > 1: merge(left)
if r_len > 1: merge(right)
# Conquer
l, r = 0, 0
while (l < l_len) & (r < r_len):
if left[l] <= right[r]:
lst.append(left[l])
l += 1
else:
lst.append(right[r])
r += 1
lst.extend(left[l:])
lst.extend(right[r:])
3.2. 힙 정렬
#!syntax cpp
#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);
}
}
#!syntax python
#python
def heapify(lst, l_len, start = 0):
i = start + 1
nxt = i * 2
while nxt <= l_len:
if nxt + 1 <= l_len:
if lst[nxt - 1] < lst[nxt]:
nxt += 1
if lst[i - 1] >= lst[nxt - 1]:
break
lst[i - 1], lst[nxt - 1] = lst[nxt - 1], lst[i - 1]
i, nxt = nxt, nxt * 2
def heap(lst):
l_len = len(lst)
for i in range(l_len // 2, -1, -1):
heapify(lst, len(lst), i)
for i in range(l_len - 1, 0, -1):
lst[0], lst[i] = lst[i], lst[0]
heapify(lst, i)
return lst
3.3. 퀵 정렬
#!syntax cpp
#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);
}
}
#!syntax python
#python using LL quicksort
def quick(lst, start=0, end=-1):
if end - start <= 1:
if end != -1:
return
end = len(lst)
left = start
pivot = lst[end - 1]
for right in range(start, end - 1):
if lst[right] < pivot:
lst[left], lst[right] = lst[right], lst[left]
left += 1
lst[left], lst[end - 1] = lst[end - 1], lst[left]
quick(lst, start, left)
quick(lst, left + 1, end)
4. 기타
4.1. 카운팅 정렬
#!syntax cpp
#include<algorithm.h>
constexpr int MAX = 100001;
void counting(int *array, int begin, int end)
{
int count_box[MAX], idx = begin, min_val = MAX, max_val = -1;
fill(count_box, count_box + MAX, 0)
for (int i = begin; i <= end; ++i)
{
int val = array[i];
count_box[val] += 1;
if (val < min_val)
{
min_val = val;
}
if (val > max_val)
{
max_val = val;
}
}
for (int i = min; i <= max; ++i)
{
int nums = count_box[i]
if (nums > 0)
{
fill(array + idx, array + idx + nums, i);
idx += nums;
}
}
}
#!syntax python
MAX = 100001
def counting (array):
ret, min_val, max_val = [], MAX, -1
temp = [0] * MAX
for i in array:
temp[i] += 1
if i < min_val:
min_val = i
if i > max_val:
max_val = i
for i in range(min_val, max_val + 1):
idx = temp[i]
if idx > 0:
ret += [i] * idx
return ret
4.2. 기수 정렬
#!syntax cpp
#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);
}