Purely Functional Data Structures & Algorithms : Selection Sort

*Updated @ 2012-08-31 02:08:58 due to internet pedantry*

Previously, previously.

According to Wikipedia :

In computer science, a Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

(A functional implementation of selection sort is however, not an in-place sort.)
Behold the abomination which is the imperative implementation (from the Wikipedia link) :

int i,j;
int iMin;

for (j = 0; j < n-1; j++) {
    iMin = j;
    for ( i = j+1; i < n; i++) {
        if (a[i] < a[iMin]) {
            iMin = i;
        }
    }

    if ( iMin != j ) {
        swap(a[j], a[iMin]);
    }
}

Now, the functional equivalent in Haskell :

selectionSort :: [Int] -> [Int] -> [Int]
selectionSort sorted [] = reverse sorted
selectionSort sorted unsorted = selectionSort (min:sorted) (delete min unsorted)
                     where min = minimum unsorted

Or in Shen :

(define selection-sort-aux
  { (list number) --> (list number) --> (list number) }
  Sorted []       -> (reverse Sorted)
  Sorted Unsorted -> (let Min (minimum Unsorted)
        (selection-sort-aux (cons Min Sorted) (remove-first Min Unsorted))))

Yes. These functional snippets use their respective implementations of the list type (which is not an efficient persistent data type in either Haskell or Shen for accesses or updates). Replacing the List type with Data.Sequence(a persistent data type with efficient constant access and update) for the Haskell snippet is trivial. I’ll leave that as an exercise to the reader. Shen is too new to support these efficient persistent types at the moment but implementations will appear in the future and changing the snippet would also be trivial. A Clojure implementation using it’s already built in efficient persistent types would also be trivial.

The complete code can be found here.

4 thoughts on “Purely Functional Data Structures & Algorithms : Selection Sort

  1. So over at reddit this post has been jumped on by the academically brain-damaged and succumbed to the usual mob screech. Any retaliation from the ‘victim’ to call out what is actually happening is buried by an insane mob of sub-humans who relish this kind of cyber abuse of individuals that will not agree with their cyber mob rule. The internet has become ugly in these places. Any kind of response on a site like reddit or ycombinator is subject to this disgusting behavior. Expect the ‘victim’ to adopt an appropriately rude and ridiculing tone in response.

    Sites that allow up-voting/down-voting are completely broken and any such discussion is a waste of time and effort. ‘Karma’ and whether or not a large group of people agree with someone’s point is hardly a model for valid discussion. It’s really just an extension of how high-schoolers arrive at ‘truth’.

    As if down-voting a comment on the internet until it’s buried actually makes it false.

    • Damn, you just described how I feel about the hive mind pretty well. I find that there’s a careful dance between saying the truth/what I actually want to say, and saying what people want to hear. HN especially, they’re a sensitive bunch.

      Some days I don’t have the energy to do the dance, and I accept the downvotes coming my way with open arms, knowing full-well I did the right thing.

  2. I was looking at Shen, and I don’t see the functions “minimum” or “remove-first” defined anywhere in the language or docs. It is pretty obvious what they do, and would be easy enough to define, but maybe they should be included or at least mention that they are missing.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>