Quicksort

Sorting algorithms are a frequent element to computer science education, conversation amongst programmers, and job interviews. There are many different versions with varying tradeoffs of performance and technique.

I noticed that Rosetta Code has a page on Quicksort implementations. I thought it might make a nice example of translating pseudocode to Factor.

simple quicksort

The "simple quicksort algorithm" has the following pseudocode:

function quicksort(array)
    less, equal, greater := three empty arrays
    if length(array) > 1  
        pivot := select any element of array
        for each x in array
            if x < pivot then add x to less
            if x = pivot then add x to equal
            if x > pivot then add x to greater
        quicksort(less)
        quicksort(greater)
        array := concatenate(less, equal, greater)

We can copy it verbatim using the ability to have named local variables:

:: quicksort ( seq -- sorted-seq )
    seq length 1 > [
        V{ } clone :> less
        V{ } clone :> equal
        V{ } clone :> greater
        seq first :> pivot
        seq [| x |
            x pivot <=> {
                { +lt+ [ x less push ] }
                { +eq+ [ x equal push ] }
                { +gt+ [ x greater push ] }
            } case
        ] each
        less quicksort equal greater quicksort 3append
    ] [ seq ] if ;

Even though local variables can be convenient, we discourage using them if library words or simpler concepts can express the same logic. Noticing that this partitions the sequence, and then joins the parts, we can make it a bit shorter using some available library words:

: quicksort ( seq -- sorted-seq )
    dup empty? [
      unclip [
          '[ _ before? ] partition [ quicksort ] bi@
      ] keep prefix append
    ] unless ;

Neither of these is particularly fast, since they involve the creation of a lot of temporary sequences. There is a better (meaning faster and not really more complex) version available.

better quicksort

The "better quicksort algorithm" is an in-place version that uses swaps to move items into a sorted order. It has the following pseudocode:

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

We can take a similar translation approach to the first example (using some unsafe words to avoid bounds-checking and mutable local variables) to create this version:

:: (quicksort) ( seq from to -- )
    from to < [
        from to + 2/ seq nth-unsafe :> pivot
        from :> left!
        to :> right!

        [ left right <= ] [
            [ left seq nth-unsafe pivot before? ]
            [ left 1 + left! ] while
            [ right seq nth-unsafe pivot after? ]
            [ right 1 - right! ] while
            left right <= [
                left right seq exchange-unsafe
                left 1 + left!
                right 1 - right!
            ] when
        ] while

        seq from right (quicksort)
        seq left to (quicksort)
    ] when ; inline recursive

: quicksort ( seq -- )
    0 over length 1 - (quicksort) ;

This is faster, although about 3x slower than our current merge sort algorithm. There are probably ways we could make it faster (one I noticed and filed an issue to track that also makes merge sort faster).

I have committed a version of this in the sorting.quick vocabulary that I hope to use for faster in-place sorting in the standard library.