Quicksort (Standard ML)

From LiteratePrograms

Jump to: navigation, search
Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

Intro

Quicksort is implemented in Standard ML in a way similar to that of most other functional languages:


The sort function does the following:

  • Choose a pivot, in this case, the midpoint of the set, for convenience.
  • Assemble a new set composed of:
    • Those elements which are less than the pivot, after the sort method is called on this new list.
    • The pivot.
    • Those elements greater than the pivot, similarly, after sort is ran on this new list.

This recursive process, of splitting the set and calling sort on each half is continued until each list is a single element (meaning it can't be sorted any further).

Explanation

The process begins with a call to the sort function. The list syntax is simplified for clarity:

sort( 5 4 3 6 7 9 8 2 1 )

  • We are choosing our pivot as the middle element of the list, rounded down, for simplicity. The list is 9 items long, so the middle is 9/2 = 4. The value at position 4 is 7 (counting from 0), so that is the pivot. (We could choose any element of the list as the pivot; a simpler solution might be to just use the first element.)
  • Our result will be a new list, composed of all the elements less than the pivot (5,4,3,6,2,1), sorted, the pivot (7), followed by all the elements greater than 7 (9, 8), also sorted. It's pretty clear that if we could sort each smaller list, we would end up with a sorted final list. So we call sort on each smaller list:

sort ( 5 4 3 6 2 1 )

(One subtlety about this method, however, is that if there are multiple copies of the pivot, we lose them, and only one will remain, because elements which are equal to the pivot will show up in neither the "left" sublist, nor the "right" sublist, and only one copy of the pivot will be inserted in the middle.)

  • Again we choose a pivot, in this case 6.
  • Our new list will be composed of the elements less than 6 (5, 4, 3, 2, 1), the pivot (6), followed by all the elements greater than 6 (). So we sort each sublist again.

sort continues to call more copies of sort, until you try to call sort on an empty list, as will have happened when we try to call sort on the set of elements greater than 6 (none). What we want to happen here is pretty clear, if we try to sort an empty list, the result is an empty list.

So we know that the right side of our sort call is an empty list (or nil, in ML terms), but we still have more work to do on the left side:

sort ( 5 4 3 2 1 )

  • The pivot is 3
  • The result is sort(2 1) + 3 + sort(5 4) [ using '+' as list concatenation ].

sort( 5 4 )

  • The pivot is 4
  • The result is () + 4 + sort(5)

sort( 5 )

  • The pivot is 5
  • The result is () + 5 + ()

The sort of (2 1) will follow a similar pattern. Once both sides have reached the end, their results will get passed back up to their parents:

  • () + 4 + sort(5)
  • () + 4 + () + 5 + ()
  • After removing the extra nils:
  • 4 + 5

... Same for sort(2 1) ...

  • sort(2 1) + 3 + sort(5 4)
  • 1 + 2 + 3 + 4 + 5

... Continuing ...

  • sort ( 5 4 3 6 2 1 )
  • 1 + 2 + 3 + 4 + 5 + 6

Finally, once all the calls are joined, the original function:

sort( 5 4 3 6 7 9 8 2 1 )

returns:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9

You may notice that each portion of the function returned a sorted list, this is a property of all divide and conquer algorithms (meaning each portion returns a portion of the final solution).

It should be pretty clear that, since the list is split in two with each call, each call will involve half as many items as it's parent did. Eventually, every path will end with an empty list (in the log2 of the number of items in the original list levels of recursion, on average).

Coding

Now we will write the code to compose the three portions of the result:

We are going to write a function with the signature: 

fn (l, p)

fn is used to create an anonymous function, meaning a function without a name. This will become a part of our sort function, not a function on its own, so it doesn't need a name. The function will take in a list, and a pivot, and return a list, composed of the portion less than the pivot, sorted, the pivot, and the portion greater than the pivot, also sorted.

The first step, is to separate the list into its three portions, to select those items less than the pivot (p): 

List.filter(fn (v) => v < p)(l)

The fn call creates a small anonymous function which returns true whenever its parameter is less than v, false otherwise. Coupled with the List.filter function, which returns every element of a list which meets some condition, it will return a list with those elements less than v. Next we call sort on this function, add p, and add the greater than portion: 

sort(List.filter(fn (v) => v < p)(l)) @ (p :: sort(List.filter(fn (v) => v > p)(l)))

The :: operator is used to add an element to the beginning of a list (p is being added to the beginning of the greater than list). The @ operator is used to concatenate two lists (the less than list is being concatenated with the list newly composed of p and the greater than list).

Finally, we compose this into the full anonymous function: 

fn (l, p) => sort(List.filter(fn (v) => v < p)(l)) @ (p :: sort(List.filter(fn (v) => v > p)(l)))

Now that we have a partitioning function, we need to call it in our sorting function. It is anonymous, so we just include the entire function: 

fun sort (l) = (fn (l, p) => sort(List.filter(fn (v) => v < p)(l)) @ (p :: sort(List.filter(fn (v) => v > p)(l))))

Next, we need to call the partitioning function we just included. Like any other function, anonymous functions are called by including their parameters in parenthesis after the function declaration. Our list, l, will also be the list inputed to the partitioning function. The pivot will be calculated by dividing the length of the list by two, and using the List.nth function, which returns a specific element of a list by its index, to get the value at that location: 

fun sort (l) = (fn (l, p) => sort(List.filter(fn (v) => v < p)(l)) @ (p :: sort(List.filter(fn (v) => v > p)(l)))) (l, List.nth(l, length(l) div 2));

This function, however, will recurse forever. We need to add an additional 'pattern', telling ML that if nil is passed to the function (as is with an empty list), to return nil: 

fun sort (nil) = nil
|   sort (l) = (fn (l, p) => sort(List.filter(fn (v) => v < p)(l)) @ (p :: sort(List.filter(fn (v) => v > p)(l)))) (l, List.nth(l, length(l) div 2));

However, creating an anonymous function and then immediately running it is kind of hard to read. So we will use the let syntax, which creates a variable that is "local" to a specific scope. We bind "p" to the pivot value; we don't need to bind "l" in this case, because it would be the same as the variable "l" that is already in the outer scope. The syntax of the let expression is let <variable and function definitions> in <body> : 

<<quicksort.ml>>=
fun sort (nil) = nil
|   sort (l) = let
                 val p = List.nth(l, length(l) div 2)
               in
                 sort(List.filter(fn (v) => v < p)(l)) @ (p :: sort(List.filter(fn (v) => v > p)(l)))
               end

That's our function!

If we include it, the ML compiler returns the following: 

val sort = fn : int list -> int list

Meaning it correctly interprets it as a function accepting a list of ints, and returning one.

Let's try running it: 

- sort([5,4,3,2,1,7,2,7,3,112]);
val it = [1,2,3,4,5,7,112] : int list

Awesome!

Note that, since lists do not support duplicate entries, the duplicate sevens and twos do not appear.

Download code
Retrieved from "http://literateprograms.org/Quicksort_%28Standard_ML%29"
Views