Patience Sort

Patience sort는 다음과 같이 작동하는 정렬 알고리즘이다. (설명이 쉽지 않다. 더 아래에 있는 코드를 보는 것을 추천한다.)

작동 과정

$n$ 장의 카드 $C_1, C_2, \cdots, C_n$이 있고, 각 카드에 수가 적혀 있다고 할 때, 우리는 다음과 같은 과정을 수행하며, 각 카드를 차례로 카드 더미에 추가한다. (카드 더미를 스택이라 생각하면 좋다. 카드 더미들은 일렬로 나열되어 있다.)

• 초기에는 아무 카드 더미가 없다. 따라서, 처음에는 카드 1장으로 이루어진 카드 더미를 하나 만들고, 해당 더미에 $C_1$을 추가한다.
• 이후, $C_2$부터 차례로 카드 더미에 다음의 규칙을 따라 추가한다.
  • 맨 위의 수가 자신보다 크거나 같은 카드 더미가 있다면, 그러한 카드 더미 중 가장 왼쪽의 "카드 더미" 위에 올려놓는다.
  • 없다면, 맨 오른쪽에 새로운 카드 더미를 만들고, 그 카드 더미에 카드를 추가한다

설명이 다소 복잡할 수 있는데, 예를 들어 카드 4장에 적힌 수가 각각 1, 4, 2, 3라고 하자. 다음과 같은 과정을 수행하게 된다.

• 1) 새로운 카드 더미 $P_1$을 만들고, 1이 적힌 카드를 $P_1$에 놓는다.
• 현재 카드 더미의 상태는 다음과 같다: $P_1 = (1)$
• 2) $P_1$의 맨 위 카드에 적힌 수는 $1 (< 4)$이다. 따라서, 새로운 카드 더미 $P_2 = (4)$을 만든다.
• 현재 카드 더미의 상태는 다음과 같다: $P_1 = (1), P_2 = (4)$
• 3) 카드 더미 $P_2$에 $2$가 적힌 카드를 올려놓는다.
• 현재 카드 더미의 상태는 다음과 같다: $P_1 = (1), P_2 = (4, 2)$
• 4) $3 > 1, 2 $이므로, 새로운 카드 더미 $P_3 = (3)$을 만든다.
• 현재 카드 더미의 상태는 다음과 같다: $P_1 = (1), P_2 = (4, 2), P_3 = (3)$.

이제, 각 카드 더미에 있는 카드는 (위에서 부터) 오름차순으로 정렬되어 있다. 다음의 과정을 $n$번 반복하여 카드를 정렬된 순서로 얻을 수 있다:

• 카드 더미 중 맨 위의 카드의 수가 가장 작은 것을 택한다.
• 해당 카드 더미의 맨 위의 카드를 꺼내온다.

시간 복잡도

시간 복잡도의 경우, 카드를 카드 더미에 추가하는 것은 이분 탐색을 통해 $O(N \log N)$에 가능하며, 카드 더미에서 카드를 꺼내 오는 것은 우선순위 큐를 이용하여 $O(N \log N)$에 가능하다. 총 시간 복잡도는 $O(N \log N)$이 된다.

특징

카드 더미에 카드를 추가하는 과정을 끝낸 후, 각 카드 더미의 맨 위에 있는 카드는 LIS(가장 긴 증가하는 부분수열)이 된다. 고로, 이 알고리즘 또한 LIS를 $O(N \log N)$에 구한다.

구현

다음과 같이 Python을 이용하여 구현할 수 있다.

 

from typing import List
import heapq

def patience_sort(L: List, inf=0x7fffffff) -> List:
    n = len(L)
    #initialize with inf for convenience
    stk = [ [inf] for _ in range(n) ] 
    for i in range(n):
        lo, hi = -1, n #(lo, hi]
        while lo + 1 < hi:
            mid = (lo + hi + 1)//2
            if stk[mid][-1] >= L[i]:
                # top element of stk[mid] < L[i]
                hi = mid
            else: lo = mid
        stk[hi].append(L[i])
    
    # merge stacks
    heap = [] # heap
    res = []
    for i in range(n):
        if stk[i][-1] != inf: # non-empty
            heapq.heappush(heap, (stk[i].pop(), i))
    for i in range(n):
        val, idx = heapq.heappop(heap)
        res.append(val)
        if stk[idx][-1] != inf: # non-empty
            heapq.heappush(heap, (stk[idx].pop(), idx))
    return res

 

다음과 같은 코드를 이용하면

• 실제로 올바르게 작동하는지,
• 그리고 Python의 내장 정렬 함수와 비교해 어느 정도의 속도로 작동하는지

평가해볼 수 있다.

##### Test Code #####

import time
import random
from functools import reduce

def test_correctness(n = 10, print_message=False):
    L = list(range(n)) + list(range(n))
    random.shuffle(L)
    if sorted(L) == patience_sort(L):
        if print_message:
            print (f'[Test Success] n = {n}, L = {L}')
        return 1
    else: 
        if print_message:
            print (f'[Test Failed] n = {n}, L = {L}, Wrong Answer: {patience_sort(L)}')
        return 0

def test_performance(N = 100000, T = 5):
    total, total_def = 0, 0
    for _ in range(T):
        L = list(range(N))
        random.shuffle(L)
        start = time.time()
        res = patience_sort(L)
        total += time.time() - start
        start = time.time()
        res = sorted(L)
        total_def += time.time() - start
    print (f'[Performance] Average elapsed time for N = {N}:')
    print (f'\tPatience Sort: {total/T:.4f} sec')
    print (f'\tPython Default Sort: {total_def/T:.4f} sec')

if __name__ == '__main__':
    random.seed(42)
    cnt = sum([test_correctness(100) for _ in range(100)])
    print (f'[Correctness] Passed {cnt} tests out of {100} tests')
    test_performance(100000)
    test_performance(500000)
    test_performance(1000000)
    test_performance(5000000)
    test_performance(10000000)

 

평가 결과는 다음과 같았다. Python 내장 정렬 함수가 약 20배 정도 빠르다.

[Correctness] Passed 100 tests out of 100 tests
[Performance] Average elapsed time for N = 100000:
        Patience Sort: 0.7759 sec
        Python Default Sort: 0.0292 sec
[Performance] Average elapsed time for N = 500000:
        Patience Sort: 4.4661 sec
        Python Default Sort: 0.2053 sec
[Performance] Average elapsed time for N = 1000000:
        Patience Sort: 9.5304 sec
        Python Default Sort: 0.4523 sec
[Performance] Average elapsed time for N = 5000000:
        Patience Sort: 55.5092 sec
        Python Default Sort: 2.8996 sec
[Performance] Average elapsed time for N = 10000000:
        Patience Sort: 114.1118 sec
        Python Default Sort: 6.4317 sec

 

다만, Python 내장 정렬 함수는 C로 구현되어 있다는걸 감안하면, 공정한 속도 비교(?)를 위해서는 C나 C++을 이용하는 편이 좋을 것 같다.