정렬 알고리즘/예제

  상위 문서: 정렬 알고리즘

1. 개요[편집]

---

정렬 알고리즘에서 소개된 각 알고리즘의 예제를 정리한 문서.

모든 알고리즘은 int형을 오름차순으로 정렬하도록 작성되었고, 현재 모든 예제는 Python과 C++를 기준으로 작성되었다.

2. O(n²)인 것[편집]

---

2.1. 버블 정렬[편집]

---

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

#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.2. 선택 정렬[편집]

---

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

#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. 삽입 정렬[편집]

---

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

#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. 이진 삽입 정렬[편집]

---

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

#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. 병합 정렬[편집]

---

#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];
        }
    }
}

#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. 힙 정렬[편집]

---

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

#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. 퀵 정렬[편집]

---

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

#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. 카운팅 정렬[편집]

---

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

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