#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil
def append(xs, ys):
if xs == Nil:
return ys
else:
return Cons(xs.head, append(xs.tail, ys))
def qsort(xs):
if xs == Nil:
return Nil
if xs.tail == Nil:
return xs
ms, vs = divide(xs.head, xs.tail)
return append(qsort(ms), Cons(xs.head, qsort(vs)))
def divide(h, xs):
if xs == Nil:
return (Nil, Nil)
ms, vs = divide(h, xs.tail)
if xs.head <= h:
return (Cons(xs.head, ms), vs)
else:
return (ms, Cons(xs.head, vs))
# demonstracni vypis
if __name__ == "__main__":
print("Radici algoritmus QuickSort\n")
print("qsort(LinkedList([5, 2, 8, 2, 654, 8, 3, 4])): \n\t%s\n" % \
qsort(LinkedList([5, 2, 8, 2, 654, 8, 3, 4])))
Radici algoritmus QuickSort
qsort(LinkedList([5, 2, 8, 2, 654, 8, 3, 4])):
[2, 2, 3, 4, 5, 8, 8, 654]
|