정렬 알고리즘

1. 개요

2. 상세

3. 안정 정렬과 불안정 정렬

4. 대표적인 정렬의 종류

4.1. O(n²)인 것

4.1.1. 버블 정렬(Bubble sort)

#!syntax cpp
void Bubble_Sort(int arr[], int len) {
  int i, j, tmp;
  for (i = 0; i < len - 1; ++i) {
    for (j = 0; j < len - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
}

#!syntax cpp
  for front_index in range(0, len(arr) - 1):
    for index in range(0, len(arr) - 1 - front_index):
        if arr[index] > arr[index + 1]:
            arr[index], arr[index + 1] = arr[index + 1], arr[index]

4.1.1.1. 파생형

• 칵테일 정렬(cocktail sort)
  
  칵테일 정렬의 과정을 나타낸 그림.

• 콤 정렬(comb sort)
  기본 형태는 버블정렬과 같지만 예를 들어 처음에 a[0]에서 10칸 띄워서 a[11]과 비교해서 치환하는 식으로 대상을 띄웠다가 한 바퀴 돌면 띄우는 간격을 좁혀서 정렬하는 방식이다. 이렇게 하면 버블정렬과 다를 게 없어졌을 시점엔 정렬이 거의 끝나 있는데, 이 단계까지 가는 동안 모양이 마치 닭의 볏을 닮았다 하여 콤 정렬이라는 이름이 붙었다. 이렇게 본다면 콤 정렬이 버블정렬보다 좋아 보이지만 단점이 있는데 버블정렬이 stable sort이지만 콤 정렬은 그렇지 못하다.

4.1.2. 선택 정렬(Selection sort)

4.1.3. 삽입 정렬(Insertion sort)

[짧은 C++ 삽입 정렬 코드]

#!syntax cpp
#include <vector>

template <typename T>
void insertionSort(std::vector<T>& vec, const int& left, const int& right){
  for (int i = left; i < right; ++i){
    for (int j = i + 1; j > left && vec[j] < vec[j - 1]; --j){
      std::swap(vec[j], vec[j - 1]);
    }
  }
}

4.2. O(n log n)인 것

4.2.1. 병합 정렬/합병 정렬(Merge sort)

4.2.2. 힙 정렬(Heap sort)

1. 원소들을 전부 힙에 삽입한다.
2. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다.
3. 힙이 빌 때까지 2의 과정을 반복한다.

4.2.3. 퀵 정렬(Quick sort)

[C++11 랜덤 피벗 퀵 정렬 예시 코드]

#!syntax cpp
#include <vector>
#include <random>

using namespace std;

random_device rd;
mt19937 mt(rd());

template <typename T>
void quickSort(vector<T>& vec, const int& left, const int& right){
  if (right <= left){
    return;
  }
  uniform_int_distribution<int> randInt(left, right);
  int leftArrow = left + 1;
  int rightArrow = right;
  swap(vec[left], vec[randInt(mt)]);
  int current = left;
  bool focusedOnRight = true;
  do {
    if (focusedOnRight){
      if (vec[current] >= vec[rightArrow]){
        swap(vec[current], vec[rightArrow]);
        current = rightArrow;
        focusedOnRight = !focusedOnRight;
      }
      --rightArrow;
    }
    else {
      if (vec[current] <= vec[leftArrow]){
        swap(vec[current], vec[leftArrow]);
        current = leftArrow;
        focusedOnRight = !focusedOnRight;
      }
      ++leftArrow;
    }
  } while (rightArrow >= leftArrow);
  quickSort(vec, left, current - 1);
  quickSort(vec, current + 1, right);
}

4.2.4. 트리 정렬(Tree sort)

1. 정렬될 배열의 맨 첫 값이 루트 노드가 된다.
2. 다음 값부터는 기존 노드 값과 비교한다. 루트 노드에서 출발해서 추가될 노드 값이 기존 노드 값보다 작은 경우는 왼쪽 자식을, 기존 노드 값보다 크거나 같을 경우는 오른쪽 자식을 찾는다. 내림차순은 반대로 기존 노드 값보다 크면 왼쪽, 작거나 같으면 오른쪽을 찾으면 된다.
3. 위 2에서 해당 방향의 자식 노드가 없으면 그 방향의 자식 노드로 추가한다. 있으면 그 방향의 자식 노드로 가서 크기를 비교하고 위 2와 같은 방법으로 해당 방향의 자식 노드가 있으면 계속 그 방향으로 가서 조사하고 없으면 그 방향의 자식 노드로 추가한다.
4. 모든 값이 노드로 추가되었으면 해당 트리를 중위 순회 방식으로 순회하여 그 순서대로 값을 정렬해 나간다.

4.3. 하이브리드 정렬

4.3.1. 팀 정렬(Tim sort)

• 핵심
• 런(run)
  전체 데이터 속 정렬되어있는 작은 구간을 run이라 부른다. 전체 데이터를 이러한 덩어리로 짜른 뒤 이를 활용하여 바텀업 병합 정렬을 시행한다.
• 병합
  두 run을 병합하는 순서는 스택과 피보나치 수 비슷한 조건을 활용하여 결정한다.
• 휴리스틱, 테크닉
• 이진 삽입 정렬
  위와 같은 방식으로 만든 run의 크기가 너무 작다면 삽입 정렬을 사용하여 특정 값(minrun, 보통 16 또는 32)이 될 때까지 정렬이 유지된 상태로 덩어리의 크기를 키운다. 병합 정렬은 원소의 개수가 적을 때 오버헤드가 발생하기 때문에 삽입 정렬이 빠르다.
• 이진 병합
  두 run을 병합할 때 병합이 필요없고 한 run만 사용해도 되는 구간을 미리 계산한다.
• 병합 중 메모리
  run A와 run B를 사용할 때 일반적인 병합 정렬은 A+B 크기의 버퍼를 사용하지만 팀 정렬은 min(A, B) 크기의 버퍼를 사용한다. 공간 복잡도는 [math(O(\frac{1}{2}n))]으로 개선되었긴 하지만 상수배의 차이이니 여전히 [math(O(n))]이다.
• 질주(galloping)
  두 run을 병합할 때 한 run만 계속 참조했다면 앞으로도 계속 그러할 것이라고 예상하고 2^k 뒤의 원소와 크기 비교를 하는 휴리스틱이다.

• 사용
• 파이썬
  애초에 파이썬을 위해 만든 알고리즘인 만큼 파이썬의 기본 정렬 함수인 sort()는 팀소트로 동작한다. 3.11부터는 팀소트의 변형인 파워소트(powersort)로 옮겨갔다.#
• 자바
  자바의 Array.sort()는 조슈아 블로크(Joshua Bloch)가 구현한 병합 정렬의 개선 버전을 사용해오고 있었는데, 팀소트가 인기를 얻기 시작하면서 자바 진영에서 이를 포팅하기 시작했다. 이후 팀소트는 여러 벤치마크 테스트에서 최대 25배까지 빠른 성능을 올리는 것으로 확인되어 자바 7이 출시될 때는 자바 컬렉션의 공식 정렬 알고리즘으로 적용되기도 했다.
• 기타
  현재 팀소트는 안드로이드 뿐만 아니라 구글 크롬, 애플의 스위프트 등 현업에서 다양하게 활용된다. 다만 고(Go) 커뮤니티에서는 팀소트가 병합 정렬을 기반으로 하기 때문에 적어도 [math(O(\frac{1}{2}n))]의 추가 메모리 공간이 필요하다는 공간 복잡도를 이유로 들어 도입을 거절하기도 했다.

4.3.2. 블록 병합 정렬(Block merge sort)

4.3.3. 인트로 정렬(Intro sort)

4.4. 그 밖에

4.4.1. 기수 정렬(Radix sort)

4.4.2. 계수 정렬(Counting sort)

4.4.2.1. 실행 과정

1. 자료를 탐색해서 그 최댓값을 구한다.
• input = [1, 5, 4, 6, 3, 7, 8, 9, 10, 2]
• 최댓값: k = 10
2. k+1만큼의 크기로 모든 자료가 0으로 초기화된 배열을 생성한다.
• 배열 counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (11개)
3. input의 모든 원소 n에 대하여 counts의 n에 대응하는 곳에 +1을 해준다.
• counts = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
• 이때 counts[n]은 배열 input에 n이 몇 개 있는지를 의미한다.
4. counts[i] += counts[i-1]의 점화식을 1부터 k의 위치까지 행한다.
• counts = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
• 이때 counts[n]은 배열 input에 n 이하의 원소가 몇 개 있는지를 의미한다.
5. 길이가 counts[k]인 배열을 하나 더 생성한다.
• 배열 ans = [N, N, N, N, N, N, N, N, N, N] (10개, N은 Null)
6. counts의 input[0]에 대응하는 곳의 원소를 찾아서 t로 놓는다. 이제 ans의 t-1에 대응하는 곳에 input[0]을 저장하고, counts의 input[0]에 대응하는 곳의 값은 -1 해준다.
• 1이 주어짐
• counts[1] = 1
• 대응하는 값인 1-1=0의 위치에 1을 삽입
• ans = [1, N, N, N, N, N, N, N, N, N]
• counts는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]에서 [0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]로 바뀜
7. 6의 과정을 남아 있는 자료에 대하여 반복한다.
• 5가 주어짐
• counts[5] = 5
• 대응하는 값인 5-1=4의 위치에 5를 삽입
• ans = [1, N, N, N, 5, N, N, N, N, N]
• counts는 [0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]에서 [0, 0, 2, 3, 4, 4, 6, 7, 8, 9, 10]로 바뀜
• ...
8. 이런 식으로 n개의 자료를 모두 조사하면 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]순서로 정렬이 된다.

4.4.3. 셸 정렬(Shell's sort)

4.4.4. 대기 정렬(Sleep sort)

#!syntax cpp
#include <chrono>
#include <string>
#include <thread>
#include <vector>

using namespace std;

int main(int argc, const char **argv)
{
    vector<string> numbers(argv + 1, argv + argc);
    vector<thread> thread_pool;

    for (const auto &number : numbers)
    {
        thread_pool.push_back(thread([number]() {
            this_thread::sleep_for(chrono::seconds(stoi(number)));

            cout << number << endl;
        }));
    }

    for (auto &thread : thread_pool)
    {
        thread.join();
    }

    return 0;
}

$ ./a.out 5 1 3 2 11 6 4
1
2
3
4
5
6
11

4.4.5. 중력 정렬(Gravity sort)

4.5. 비효율적인 정렬

4.5.1. 스투지 정렬(Stooge sort)

• 구간 전체에서 첫 번째 요소와 마지막 요소를 비교하여 정렬한다.
• 요소가 세 개 이상일 경우, 다음의 과정을 거친다.
• 구간 전체의 앞쪽 2/3에 해당하는 구간(올림)에서 스투지 정렬을 수행한다.
• 구간 전체의 뒤쪽 2/3에 해당하는 구간(올림)에서 스투지 정렬을 수행한다.
• 구간 전체의 앞쪽 2/3에 해당하는 구간(올림)에서 다시 스투지 정렬을 수행한다.

4.5.2. 보고 정렬(Bogo sort, stupid sort)

4.5.3. 보고보고 정렬(Bogobogo sort)

1. 검사되어야 할 데이터의 카피를 만든다.
2. 그 중 첫 n-1개의 데이터를 보고보고 정렬한다.
3. n번째 숫자가 첫 n개의 데이터 중에서 가장 큰지 확인한다. 그렇다면 이 데이터는 정렬되었다. 아니라면 랜덤으로 데이터를 섞은 뒤 2로 돌아간다.
4. 이 리스트가 원래의 리스트와 순서가 같은지 검사한다. 맞다면 이 리스트는 정렬된 것이다.

5. 관련 문서

• 수학 관련 정보
• 컴퓨터 관련 정보
• 정렬 알고리즘/예제
• 점근 표기법
• 프로그래밍 언어
• 자료구조
• 알고리즘