Skip to content

Instantly share code, notes, and snippets.

@narskidan

narskidan/qsort.hoon

Last active November 14, 2023 04:57
Show Gist options
  • Save narskidan/fd746a6c1a443fd7244d7bfb957a9260 to your computer and use it in GitHub Desktop.
Save narskidan/fd746a6c1a443fd7244d7bfb957a9260 to your computer and use it in GitHub Desktop.
Download ZIP
Quicksort in Hoon!
Raw
qsort.hoon
|= l=(list @ud)
^- (list @ud)
?: =(0 (lent l))
~
=/ pivot (snag 0 l)
=/ rest (slag 1 l)
=/ less (skim rest |=(a=@ (lte a pivot)))
=/ more (skim rest |=(a=@ (gth a pivot)))
:(weld $(l less) ~[pivot] $(l more))
@narskidan
Copy link
Author

Quick (ha) reference implementation I wrote in Python of how the Hoon code "should" work:

def qsort(l):
    if len(l) == 0: return []
    pivot = l[0]
    less = qsort([i for i in l[1:] if i <= pivot])
    more = qsort([i for i in l[1:] if i > pivot])
    return less + [pivot] + more

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment