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

According to Wikipedia :

InΒ computer science, aΒ

Selection sortΒ is aΒ sorting algorithm, specifically anΒ in-placeΒ comparison sort. It hasΒ O(n^{2}) 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.