QuickSort in Functional Programming

일전에 포스팅하여 설명한 바 있는 퀵소트는 제자리정렬 (추가적으로 메모리를 사용하지 않고 배열 내 원소들의 위치를 바꿔가며 정렬)이지만 함수형 프로그래밍 언어에서는 모든 ‘값’이 상수이므로 변경이 불가하여 이를 적용할 수 없다. 결국 퀵소트를 구현하려고하면 제자리 정렬을 하는 대신 계속해서 부분집합의 사본을 만들게되는데, 그럼에도 불구하고 함수형 언어의 문법들은 수학적 표현과 관련이 깊기 때문에 더 간단하게 표현되는 경우가 많다. 하스켈로 표현한 퀵소트의 경우를 보자.

qsort :: [Num] -> [Num]
qsort [] = []
qsort (x:xs) = let pivot = x
                   less = filter (<pivot) xs
                   greater = filter (>=pivot) xs
                in (qsort less) ++ (pivot : (qsort greater))

위 코드는 말 그대로 리스트의 맨 첫 원소를 피봇으로 하고 피봇보다 작은 값은 less라는 부분집합으로, 그보다 크거나 같은 값은 greater라는 부분집합으로 만든 뒤, 크기 순으로 (다시 정렬한) less, pivot, (다시 정렬한) greater를 이어 붙인다.

리스트에 대한 필터 함수가 핵심이라 파이썬에서도 이를 따라할 수 있다.

def qsort(alist):
    if len(alist) is 0:
        return []
    pivot = alist[0]
    less = filter(lambda x:x<pivot, alist[1:])
    greater = filter(lambda x:x>=pivot, alist[1:])
    return qsort(less) + [pivot] + qsort(greater)

Swift에서도 되는 건 두말할 필요가 없겠다.

func qsort<T:Compareable>(alist:[T]) -> [T] {
    if list.count == 0 return []
    let pivot = list[0]
    let tail = Array(dropFirst(alist))
    var less = qsort(tail.filter{ $0 < pivot })
    let greater = qsort(tail.filter{ $0 >= pivot })
    less += [pivot]
    less += greater
    return less
}