정렬 알고리즘/예제

1. 개요

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);
}