정렬 알고리즘

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(front_index + 1, len(arr)):
      if arr[front_index]>arr[index]:
        arr[front_index],arr[index]=arr[index],arr[front_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)

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)

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

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

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

5. 관련 문서

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