Quick Sort

 Haskell로 Quick Sort를 만들면 2줄로 간단히 나온다.

quicksort []       =  []
quicksort (x:xs)  = quicksort[y | y <- xs, y < x] ++ [x] ++ quicksort[y | y <- xs, y >= x]

Python 도 유사하게 구현이 가능하다.
 

import random

def qsort(list):
   
    if len(list) <= 1:
        return list

    pivot = random.choice(list)
    list.remove(pivot)
   
    return qsort([it for it in list if it < pivot]) + [pivot] + qsort([it for it in list if it >= pivot])

* Test code

#----------------------------------------------------------
# main
if __name__ == "__main__":

    before_sort = [1, 4, 2, 7, 9, 8, 3, 6, 5, 5]
    random.seed()

    print before_sort;
    after_sort = qsort(before_sort)
    print after_sort;  

* 실행결과

[1, 4, 2, 7, 9, 8, 3, 6, 5, 5]
[1, 2, 3, 4, 5, 5, 6, 7, 8, 9]