True QuickSort in Standard ML

Question

Since RosettaCode's Standard ML solution is a very slow version of Quicksort according to the question (and discussion) "Why is the minimalist, example Haskell quicksort not a "true" quicksort?", how would a functional Quicksort look like in Standard ML if it behaved according to the complexity of Hoare's algoritm?

fun quicksort [] = []
  | quicksort (x::xs) =
    let 
        val (left, right) = List.partition (fn y => y<x) xs
    in
        quicksort left @ [x] @ quicksort right
    end

That is, one that employs some aspects of functional programming where it makes sense. Unlike the Haskell version that needs to encapsulate its in-place partitioning, would there be any need for a Quicksort in SML to vary in any way from the C version besides syntax? Whether the function accepts an array/vector or spends O(n) time converting the list is less relevant.

Edit: Rephrased question with regards to John Coleman's comments.

With the impure parts of SML involving `ref`, mutable arrays, loops, etc., it is of course somewhat easy to write an imperative in-place quicksort. The interesting question is if you can write a quicksort in SML that is both efficient and (mostly) functional. — John Coleman, Feb 08 '17 at 04:20

score 2 · Accepted Answer · answered Feb 11 '17 at 05:34

Here is my attempt:

fun swap(A,i,j) = 
    let
        val t = Array.sub(A,i)
    in
        Array.update(A,i,Array.sub(A,j));
        Array.update(A,j,t)
    end

fun firstAfter(A,i,f) =
    if f(Array.sub(A,i)) then i else firstAfter(A,i+1,f)

fun lastBefore(A,j,f) =
    if f(Array.sub(A,j)) then j else lastBefore(A,j-1,f)

fun partition(A,lo,hi)=
    let 
        fun partition'(A,lo,hi,pivot) = 
            let 
                val i = firstAfter(A,lo,fn k => k >= pivot)
                val j = lastBefore(A,hi,fn k => k <= pivot)
            in
                if i >= j then 
                    j
                else
                (
                    swap(A,i,j);
                    partition'(A,i+1,j-1,pivot)
                 )
             end
   in
      partition'(A,lo,hi,Array.sub(A,lo))
   end

fun quicksort(A,lo,hi) = 
    if hi <= lo then
        ()
    else
        let
            val p = partition(A,lo,hi)
        in
            (
                quicksort(A,lo,p);
                quicksort(A,p+1,hi)
             )
        end;

fun qsort A = quicksort(A,0,Array.length A - 1);

It follows Hoare's algorithm as described in Wikipedia fairly closely but uses recursion rather than loops, and has a somewhat functional approach for looking for pairs of indices to swap. There is no question that this is nowhere nearly as elegant as the 2 or 3 line pseudo-quicksort which is often taught in introductory treatments of functional programming and it doesn't really showcase the powers of functional programming. Hopefully someone who knows more SML than I can come up with a more idiomatic SML qsort.

score 1 · Answer 2 · answered Apr 13 '21 at 12:11

You can find some of sorting algorithms written in Standard ML in my github repository https://github.com/Khanzadeh-AH/sorting_algorithms_SML

fun pivot_split([], pivot) = ([],[])
|   pivot_split(h::t, pivot) =

        let
            val (L,R) = pivot_split(t, pivot)
        in

            if h < pivot then (h::L, R)
            else (L, h::R)
        end;
    
    

fun quicksort([]) = []
|   quicksort([a]) = [a]
|   quicksort(h::t) =
        let
            val (L, R) = pivot_split(t, h)
        in
            quicksort(L)@[h]@quicksort(R)
        end;



pivot_split([12,3,5,67,1,2,3,5,7],3);

quicksort([12,3,5,67,1,2,3,5,7]);

A'hoy, @Khanzadeh_AH. The "QuickSort" you provide is exactly not a true QuickSort. If you don't know why, you can read the article [Forward Is Not Enough](https://www.informit.com/articles/article.aspx?p=1407357&seqNum=3). Feel free to ask questions if the reasoning is not spelled out enough. — sshine, Apr 13 '21 at 20:19

True QuickSort in Standard ML

2 Answers2

Linked