본문 바로가기

Computer Science/Algorithms & Problem Solving

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++을 이용하는 편이 좋을 것 같다.

'Computer Science > Algorithms & Problem Solving' 카테고리의 다른 글

2021-08-01 Problem Solving  (0) 2021.08.01
Generalized Sorting with Predictions  (0) 2021.05.05
Minimums on the Edges 풀이  (0) 2020.10.19
최대 부분합과 쿼리  (0) 2020.06.06
Patience Sort  (0) 2020.05.24
Kruskal's Algorithm과 MST의 성질  (0) 2020.03.13