Another challenge: can you write a correct selection sort?

Horribly inefficient, but seems to work for random, reverse ordered, empty, arrays with duplicated values, and single element arrays.

def selectionSort(array):
  """
    Find the minimum and recursivley build the resulting array.
  """

  if (len(array) < 1):
    return []

  min = array[0]
  mini = 0
  i = 1

  while (i < len(array)):
    if array[i] < min:
      min = array[i]
      mini = i

    i = i + 1

  # Build array missing min
  newarray = array[:mini] + array[mini+1:]

  return [min] + selectionSort(newarray)

In retrospect, I’m not sure if the problem requires an in place sort or not, so I may be cheating.

Similarly not in-place.

selection :: (Ord a) => [a] -> [a]
selection [] = []
selection xs = let x = foldl1 min xs
               in x : selection (skip1 x xs)
    where
      skip1 y [] = []
      skip1 y (n:ns) = if y == n 
                       then ns 
                       else n : skip1 y ns

I love these.

Not tested, just compiled.

template<typename raIterator>
void selection_sort(raIterator begin, raIterator end)
{
    while(begin != end)
    {
        raIterator smallest = begin;
        raIterator next = begin + 1;

        while(next != end)
        {
            if(*next < *smallest)
            {
                smallest = next;
            }

            ++next;
        }

        std::swap(*smallest, *begin);

        ++begin;
    }
}

Hm. I used the name “raIterator” to imply that the iterator should be random-access (like in the binary sort problem), but really, this will work just fine with a sequential-access iterator.

Oh well.

OK, I had a moment so I’ll give this one a crack. Fifteen minutes start to finish. C99 because of the variable-sized array. No standard libs. No testing.

#include <stdbool.h>
void selection_sort( int input[], int output[], unsigned int len ) {
	if (len > 0) {
		bool used[len];
		for (unsigned int i=0; i<len; ++i)
			used[i] = false;
		for (unsigned int dst=0; dst<len; ++dst) {
			bool first = true;
			unsigned int src = 0;
			for (unsigned int search=0; search<len; ++search) {
				if (!used[search] && (first || (input[search] < input[src]))) {
					src = search;
					first = false;
				}
			}
			used[src] = true;
			output[dst] = input[src];
		}
	}
}

I forgot to do swap using Temp var and directly assigned smallest value to current index :-|
Time taken ~15mins

//c#
        static void Main(string[] args)
        {
            
                int[] numbers = { 12, 85, 45, 73, 5, 99, 108 };
                for (int idx = 0; idx <= numbers.Length - 1; idx++)                
                    Console.Write(numbers[idx] + " ");
                
                Console.WriteLine();
                int smallest = 0;
                int temp = 0;
                for (int i = 0; i <= numbers.Length - 1; i++)
                {
                    smallest = i;
                    for (int j = i + 1; j <= numbers.Length - 1; j++)                    
                        if (numbers[smallest] > numbers[j])                        
                            smallest = j;                        
                    
                    temp = numbers[i];
                    numbers[i] = numbers[smallest];
                    numbers[smallest] = temp;
                }

                for (int idx = 0; idx <= numbers.Length - 1; idx++)                
                    Console.Write(numbers[idx] + " ");
                
                Console.WriteLine(); 
                Console.Read();
         }

[cont. edit] so it worked in 2nd try.. after using temp.

is there any punishment ? :-S

In place is fine, and is what I had in mind; but returning a sorted equivalent array is also fine.

I’ll tweak the article to clarify that.

def ssort( list ):
    sorted_list = []
    while list:
        current_lowest = 0
        for i in range( len(list) ):
            if list[i] < list[current_lowest]:
                current_lowest = i
        sorted_list.append( list.pop( current_lowest ) )
    return sorted_list

I could make it not destructive with a simple array copy. I chose not to do inline sorting because that would have greatly increased the chance of me making a subtle mistake. :)

Worked perfect on all types of int arrays and empty arrays on first test. Should work with anything that implements __gt__ and __lt__.

Just to use the language that everyone loves to hate (and it seems to work):

    public static void sort(int[] values) {
	sortFrom(values, 0);
    }

    public static void sortFrom(int[] values, int lowIndex) {

	if (lowIndex >= values.length) return;
	int minValue = values[lowIndex];
	int minIndex = lowIndex;
	for(int i = lowIndex+1; i < values.length; i++) {
	    if (values[i] < minValue) {
		minValue = values[i];
		minIndex = i;
	    }
	}
	int t = values[lowIndex];
	values[lowIndex] = values[minIndex];
	values[minIndex] = t;
	sortFrom(values, lowIndex+1);
    }

Corey Porter, I’m not sure if it isn’t cheating a bit to use a min function, as it does half of the problem for you. (Obviously doesn’t count as cheating in your case since you did it before I’d spelled that out.) I’ll tweak the rules to make that clearer.

Used C++ for this. I made a stupid typo and forgot the * in if (*k > *biggest), so it didn’t sort at all the first run through.

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
vector<T> sort_list(vector<T> &source)
{
    vector<T> dest;
    for(int i = source.size(); i > 0; i--)
    {
        typename vector<T>::iterator biggest = source.begin();
        typename vector<T>::iterator k = source.begin();
        for (int j = 0; j < i; j++, k++)
        {
            if (*k > *biggest) biggest = k;
        }
        T val = *biggest;
        source.erase(biggest);
        dest.insert(dest.begin(), val);
    }

    return dest;
}

int main()
{
    vector<int> source_list;

    source_list.push_back(53);
    source_list.push_back(1);
    source_list.push_back(1337);
    source_list.push_back(-42);

    vector<int> sorted_list = sort_list(source_list);
    for(vector<int>::iterator i = sorted_list.begin(); i != sorted_list.end(); i++)
    {
        cout << *i << endl;
    }

    return 0;
}

Tested zero, 1, all minvalue, all maxvalue, random arrays and it worked on the first try. There is the possibility of unnecessary swaps when there are duplicate values, but it is correct AFAIK.
[Code]
static void Sort(int[] array)
{
int x = 0;
while (x = array.Length) { throw new ApplicationException(); }
for (int x = start; x < array.Length; x++)
{
if (array[x] <= lowestValue) { lowestIndex = x; lowestValue = array[x]; }
}
return lowestIndex;
}
[/Code]

Whoops, got the tag wrong, second try:
[Source]
static void Sort(int[] array)
{
int x = 0;
while (x = array.Length) { throw new ApplicationException(); }
for (int x = start; x < array.Length; x++)
{
if (array[x] <= lowestValue) { lowestIndex = x; lowestValue = array[x]; }
}
return lowestIndex;
}
[/Source]

Compiled but completely untested (makes me nervous). Took about 15 minutes. It’s an iteration/recursion hybrid using Common Lisp:

(defun selection-sort! (array &optional (start 0))
  "Destructively sorts the numeric array in ascending order starting at index START."
  (if (>= start (length array))
    array
    (loop
       for i from start below (length array)
       for val = (elt array i)
       with min-index = start
       with min-value = (elt array start)
       do (when (< val min-value)
            (setf min-index i
                  min-value val))
       finally (progn
                 ;; This swaps elements in the array.
                 ;; Note: it's a noop when (= start min-index)
                 (rotatef (elt array start)
                          (elt array min-index))
                 ;; Recursively sort the next subarray (which may be empty).
                 (return (selection-sort! array (1+ start)))))))

def insort(v):
  for i in range(len(v)):
    min_idx = v.index(min(v[i:]), i)
    v[i], v[min_idx] = v[min_idx], v[i]

In-place, horribly inefficient (scans the unsorted portion twice as often as it needs to). Failed first time round, as I missed off the ‘, i)’ – shameful.

My conscience was happy with the use of ‘min’ though, since a) I’d coded it before the rules changed, and b) the ‘trick’ is calling ‘min’ over the correct sub-sequence.

The code (Java):

public static int[] selectionSort(int[] input) {
	if (input == null)	// Is there a list?
		return input;
	else if (input.length <= 1)	// Does it need sorting?
		return input;

	int start = 0;
	int end = input.length - 1;

	while (end > start) {
		int min = input[start];
		int minIndex = start;

		for (int i = start + 1; i <= end; i++) {
			int num = input[i];

			if (num < min) {
				min = num;
				minIndex = i;
			}
		}

		if (minIndex != start) {
			int temp = input[start];
			input[start] = input[minIndex];
			input[minIndex] = temp;
		}

		start++;
	}

	return input;
}

Does it work? Perfectly! Do I pass? No.

See, I made one mistake. One little mistake. Those three lines where I swap values? I used the variable name “index” instead of “input”. I didn’t catch this until I pasted my code into Eclipse (I wrote it in Notepad). Once that was fixed, it worked perfectly.

But my testing harness didn’t. That took two runs. My little function to print out the arrays had two simple bugs in it, stupid bugs. The kind that are easily caught when you run the program. The kind you don’t make when you actually think about what you’re writing.

Tested with null input, one number input, sorted input, descending sorted input, and mixed input.

Failed with:

def selection_sort(the_list):
    list_len = len(the_list)
    outer = 0
    while outer < list_len - 1:
        inner = outer + 1
        smallest = None
        while inner < list_len:
            if smallest == None:
                smallest = inner
            elif the_list[inner] < the_list[smallest]:
                smallest = inner
            inner += 1
        if smallest:
            swap = the_list[outer]
            the_list[outer] = the_list[inner]
            the_list[inner] = swap
        outer += 1
    return the_list

Three bugs:

1. Failed to include the starting point in the search for the smallest remaining value.

2. Forgot to test for a need to swap.

3. Used inner instead of smallest as index when swapping.

Passes with:

def selection_sort(the_list):
    list_len = len(the_list)
    outer = 0
    while outer < list_len - 1:
        inner = outer
        smallest = None
        while inner < list_len:
            if smallest == None:
                smallest = inner
            elif the_list[inner] < the_list[smallest]:
                smallest = inner
            inner += 1
        if smallest and smallest > outer:
            swap = the_list[outer]
            the_list[outer] = the_list[smallest]
            the_list[smallest] = swap
        outer += 1
    return the_list

My test cases:

test_list = [9, 7, 5, 3, 1]
print test_list, selection_sort(test_list)
test_list = [2, 4, 6, 8]
print test_list, selection_sort(test_list)
test_list = []
print test_list, selection_sort(test_list)
test_list = [1, 8, 4, 6, 5, 2]
print test_list, selection_sort(test_list)
test_list = [2, 4]
print test_list, selection_sort(test_list)
test_list = [5, 3]
print test_list, selection_sort(test_list)
test_list = [999]
print test_list, selection_sort(test_list)

I wrote this iteratively, not recursively. It took me 5 minutes to write, and then 10-15 minutes careful hand-testing to persuade myself it was correct. I then formally tested it against an empty array, a 1 element array a 2 element array, a 3 element array and a 10-element array. I think the algorithm can be shown to be provably correct (in terms of bounds, invariants, etc) with no more than 3 elements in the array: i.e. if it is provably correct for 0..3 elements, then it is true for 0..n.

Here’s the code

	static void sort(int[] a, int n) {
		for (int i = 0; i < n; i++) {
			int k = i;
			int v = a[k];
			for (int j = i+1; j < n; j++) {
				if (a[j] < v) {
					v = a[j];
					k = j;
				}		
			}
			if (k > i) {
				a[k] = a[i];
				a[i] = v;
			}
		}
	}

I’m happy to say it passed all the tests!

Whew, yeah. A little nervous actually hitting run, and I had to do an experiment to remind myself how to work with C++ arrays.

/**
 * Sort an array of integers using selection sort,
 * an O(n^2) algorithm that works by picking the smallest element
 * and putting it in the first spot, then picking the second
 * smallest element and putting it in the second spot, and so on
 * until the array is sorted.
 *
 * Preconditions: a is an array of integers
 * Postconditions: For every integer a[i], where i > 0, 
 *                 a[i] >= a[i-1]
 * 
 * @param[in,out] a the data to sort
 * @param[in] numElements the size of the array
 */
void SelectionSort(int a[], const int numElements) {
  if ((!a) || (numElements == 0)) // nothing to do
    return;

  // For every integer a[i], where 0 < i < iSortedUntil, a[i] >= a[i-1]
  for (int iSortedUntil = 0; iSortedUntil < numElements; iSortedUntil++) {

    // Find the smallest element in the rest of the array
    int iSmallestElement = iSortedUntil;
    for (int iElement = iSortedUntil; iElement < numElements; iElement++) {
      if (a[iElement] < a[iSmallestElement]) {
        iSmallestElement = iElement;
      }
    }

    // Swap the smallest element into the smallest remaining index
    int tempValue = a[iSortedUntil];
    a[iSortedUntil] = a[iSmallestElement];
    a[iSmallestElement] = tempValue;
  }
}

void selection_sort(int *array, size_t size) {
size_t i, k = 0, idx;
int tmp;
for (k = 0; k < size; ++k) {
idx = k;
for (i = k+1; i < size; ++i)
if (array[i] < array[idx])
idx = i;

if (idx != k){
tmp = array[k];
array[k] = array[idx];
array[idx] = tmp;
}
}
}

Here is my try in python:

def sort(a):
    idx = 0
    min_idx = 0
    while idx < len(a)-1:
        for i in range(idx, len(a)):
            if a[i] < a[min_idx]:
                min_idx = i
        a[idx], a[min_idx] = a[min_idx], a[idx]
        idx += 1
        min_idx = idx
    return a

I spent on it less than 10 minutes (I didn’t measure exactly). This code is the first attempt. It seems to work fine… Hopefully I didn’t overlook something. Unfortunately it does not look very pythonic ;)

Whoops, forgot to include: it passed my quick set of tests when I ran it

David Gladfelter, have a third try, but this time make your source tags all lower-case. If you also repeat the notes from your first try, I’ll delete the first two (and this message) so only your good one remains. (I can’t fix it up for you because in the absence of correct source tags, WordPress eats sequences beginning with less-than.)

Heh I managed to fail, forgot the array indices I think.

   public static void selectionSort(int[] list){
        if(list!= null && list.length>0){
            int n = list.length-1;
            for(int i=0; i<n-1;i++){
                for(int j=i+1; j<n; j++){
                    if(list[j]<=list[i]){
                        int temp = list[j];
                        list[j] = list [i];
                        list[i] = temp;
                    }
                }
            }
        }

I wrote mine in C, it sorts in place.

void selection_sort(int *array, size_t size) {
    size_t i, k = 0, idx;

    if (array == NULL || size == 0)
        return;

    for (k = 0; k < size; ++k) {
        int tmp;
        idx = k;
        for (i = k+1; i < size; ++i)
            if (array[i] < array[idx])
                idx = i;

        if (idx != k){
            tmp = array[k];
            array[k] = array[idx];
            array[idx] = tmp;
        }
    }
}

Straight-up naive recursion, in Scheme:

(define (min L)
     (let ((x (min (cdr L))))
            (if (< (car L) x) (car L) x)))

(define (removefirst x L)
     (if (null? L) '()
           (if (eq? x (car L)) (cdr L)
                 (cons (car L) (removefirst x (cdr L))))))

(define (selectsort L)
     (if (null? L) '()
           (let ((x (min L)))
                   (cons x (selectsort (removefirst x L))))))

I’m waiting to see the Haskell solutions.
Wasn’t sure what the pitfalls are for this algorithm. Function worked first time. The one part that gave me pause was also commented on in earlier comments — whether better to test if swap needed (would seem to depend on whether input is well-sorted or poorly-sorted). I assumed poorly:

/* Passing in an unsorted array T of length N
 * returns the array sorted in-place
 */
void selsort(int T[],int N)
{
int j,k,min_i;
int v;

    for(j=0;j<N;j++)
    {
        min_i = j;
        v = T[j];
        for(k=(j+1);k<N;k++)
        {
            if( T[k]<v )
            {
                min_i = k;
                v = T[min_i];
            }
        }
        /* swap values */
        T[min_i] = T[j];
        T[j] = v;
    }
    return;
}

def selectionSort(myarray)
  if (myarray.length > 1) 
    @index = 0
    @toobig = myarray.length 
    while (@index<@toobig)
      @min = myarray[@index]
      @minindex = @index
      @scan = @index+1
      while (@scan<@toobig)
        if (myarray[@scan]<@min) 
          @min = myarray[@scan]
          @minindex = @scan
        end
        @scan += 1
      end
      if (@minindex != @index)
        myarray[@index],myarray[@minindex] = myarray[@minindex],myarray[@index]
      end
      @index += 1
    end
  end
  return myarray
end

I could probably make it “more clever” with some work and better ruby syntax, but it seems “clever enough”. Doesn’t choke on null arrays, singleton arrays, negative values or other similar things. Note that the value swap is only safe because ruby specifically turns that syntax into something safe.

Here’s my take in ruby – passed all the tests, took around 15 minutes.

def sort array
  size = array.size

  (0...size).entries.each do |index|
    min = index

    (index...size).entries.each do |subindex|
      min = subindex if array[min] > array[subindex]
    end

    array[index], array[min] = array[min], array[index]
  end

  array
end

Process:
Write code and notes.
Fix syntax errors.
Describe why the code ought to be correct.
Submit here.
Test?
(Reformatting the text from the current “source code comment” is not part of this process.)

Hopefully, WordPress will format OCaml sensibly as F#… (And with luck, the big pile of texts-as-comment will look OK…)

let selection_sort arr =
  let swap i j =
    let temp = arr.(i) in
      arr.(i) <- arr.(j);
      arr.(j) <- temp
  and smallest_from from =
    let selected = ref from in
      for i = from + 1 to Array.length arr - 1 do
	if arr.(i) < arr.(!selected) then
	  selected := i
      done;
      !selected
  in
    for i = 0 to Array.length arr - 1 do
      swap i (smallest_from i)
    done


(*
  Notes:
  Arrays and imperative code in OCaml --- for fun...
  And I'd forgotten that for loops in OCaml are terminated by "done"...
  Arrays with index from 0 and for-loops with a closed [from, to] range; the combination is slightly annoying...


  Arguments for correctness:

  swap : Assumes valid indexes in input, wastes a bit of time when i = j, there shouldn't be other edge cases...?  (Paranoia-mode...)

  smallest_from : Assumes valid index as input.  Internal loop will not go beyond end of array; might not run at all.  (Loop invariant: "selected" a reference to index smallest value in range [from, i].  (Well, OK, "i" is incremented before "selected" is updated; but I'm not altering the code to make the loop invariant prettier.)  Loop *will* terminate; finite range and "manually" messing with the loop counter is not possible...)  Returned value is a valid index in range [from, last-valid-index].  If the loop is not run, we have that "from" is the last valid index, and thus automatically the smallest in the range --- otherwise, it will be the smallest from the loop invariant as the loop terminates after i = last-valid-index.

  main loop : The first "i" positions (i.e. index 0, ..., i-1) in the array contains the smallest "i" values.  Trivially holds for i=0; and we put the right thing at index i before incrementing.


  For an empty array, we do nothing.
  For an array with 1 element, we swap it with itself --- silly, but shouldn't hurt.

  There shouldn't be any edge cases for "large" arrays for this.
  This code *assumes* that the result from Array.length is sensible; in the range [0, max_int], and subtracting 1 is valid for each of those; any valid index is in the range [0, max_int - 1]; adding 1 is valid for each of those.
  Besides; due to limitations in the OCaml standard library Array, valid array lengths aren't even close to the upper limits...
  (And...  Using a selection sort for anything "big" would not be a good idea anyway...)

*)

I didn’t do the binary search one primarily because I didn’t understand or agree with your “no testing” rule. I’m joining in now, after reading the explanation and agreeing with it.

I must say, I think selection sort is significantly easier than binary search, though I don’t know why. I’m fairly certain that I’d make all the usual mistakes if I were to write a binary search, but writing selection sort would come fairly easy even without the invariant comments in my code ahead. Though they did help me organize my thoughts when I wrote the code.

Please don’t judge the comments: it’s after 1am in my timezone and I should be sleeping, not coding.

Compiled and tested, failed miserably: I reversed the test in the middle, which means all my arrays are sorted in reverse order. I won’t blame the hour for this, I could have just as easily made this mistake wide awake. It’s just, this particular bit of code (find the minimal element) is so idiomatic that I write it without thinking, and therefore get it wrong with probability 50%.

void sel_sort(int a[], int size) {
    int max_sorted = 0; // Invariant: elements of a up to (not including) max_sorted are the correct ones.
    // I.e., a[0..m_s-1] are all in order and all less than a[m_s..size-1]

    // Additional ("obvious") invariant: the elements of a don't change, only their order.

    while (max_sorted < size) {
        int i;
        int min_index = max_sorted, min_el = a[min_index]; // Invariant: min_el == a[min_index];
        for (i=max_sorted; i < size; i++) {
            if (min_el < a[i]) {
                min_index = i;
                min_el = a[min_index];
            }
        } // Post-condition: min_el is the minimum of the not-yet-sorted elements
        // This means that a[max_sorted] should be == min_el after this next transformation.

        a[min_index] = a[max_sorted];
        a[max_sorted] = min_el;
        // This was parts two and three of "t=a a=b b=t", with part 1 being in the loop above. Therefore the "obvious" invariant is preserved.

        // Now: We didn't touch a[0..m_s-1], and we put the next min element in a[m_s], so a[0..m_s] are all in order. This means that the invariant is preserved if we do:
        max_sorted++;
    } // Post-condition: max_sorted == size, so a is sorted
}

Missed out last time because I started hacking at it before I finished reading the article, so glad to give it a try now. Submission is a python function that accepts a list of ints as it’s only parameter. Also, typing solution directly into comment. If you plan on making a habit of this, you might want to look into http://www.spoj.pl/, automated programming contest software. I seem to recall that they have some kind of system where you can define your own challenges, along with test suites, etc..

#preconditions: Accepts a list of size sys.maxsize or smaller containing nothing but integers.
#maximum size of integers handled is sys.maxint, larger integers are not handled
#postconditions: Returns an array with the same contents as the input array, but with the contents in sorted order
#note: this is an unstable sort!  obviously it doesn't matter with integers, but if we were sorting on items with additional state this could be problematic.
#performance should be absolutely abysmal, on the order of O(n^2+n^2) depending on the implementation of several python statements.
from sys import maxint
def select_sort(unsorted_list):
  sorted_list = []
  while len(unsorted_list > 0):
    smallest = maxint
    smallest = reduce(lambda a,b: (b <= a if b else a) unsorted_list), unsorted_list, smallest)
    unsorted_list.remove(smallest)
    sorted_list.append(smallest)
  return sorted_list

Coded in C, sorts an array in-place. Wrote it, eyeballed to convince myself it was correct, but wasn’t quite brave enough to submit without running through a few simple tests.

void sort (int a[], int n) {
    for (int i = 0; i < n; i++) {
        int min = a[i], min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < min) {
                min = a[j];
                min_idx = j;
            }
        }
        int tmp = a[i];
        a[i] = a[min_idx];
        a[min_idx] = tmp;
    }
}

@Mike Taylor/Corey Porter:
That’s Haskell, and the “min” function is the kind which takes two values and returns the smaller, i.e. something like “x < y ? x : y" in C.
Using that with fold *does* make things simple, but that's just Haskell… (Though we could do something very similar with a combination of std::min and std::accumulate in C++… And, of course, the elegant solutions in Haskell won't sort in-place…)

Untested. Hope I don’t regret this:

int min(int * arr, size_t size)
{
    int m = 0;
    int i;

    for (i = 0; i < size; ++i)
    {
        if (arr[i] < arr[m])
           m = i;
    }
    return m;
} 

void swap(int * arr, int x, int y)
{
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}

/* Sorts an array in place using the selection sort algorithm.
 *
 * precondition:
 *      arr is a pointer to an array of zero or more ints.
 *      size is the number of ints in the array that arr points to.
 * postcondition:
 *      The array that arr points to contains all the ints it began with sorted
 *      in ascending order. 
 */
int * selectionsort(int * arr, size_t size)
{
    int m;
    int s; /* number of ints sorted */

    /* invariant:
     *     arr[i] <= arr[i+1] for any index i < s. 
     *     arr[i] <= arr[j] for any indices i and j where i < s and j >= s.
     * bound function: size - 1 
     */
    for (s = 0; s < size - 1; ++s) 
    {
        m = min(arr + s, size - s);
        swap(arr, m, s);
    }
    return arr;
}

These exercises are pretty fun, by the way.

Great. Line 42 of my solution is wrong. It needs to be:

        m = min(arr + s, size - s) + s;

min is returning an index that’s counted from the beginning of the chunk of the array it’s looking at, not the entire array, so the swap wasn’t given the correct index. Whoops.

Arild, its fascinating to see which programming languages hide which parts of the complexity. I can’t really justify this, but I feel that using a min() function that finds the smallest value in an array is (just) cheating, whereas a function that only chooses the lesser of two values is legitimate; and of course when the language lets you fold that along an array, you end up where you started. Bottom line seems to be that doing it in a more spelled-out-element-by-element array would just not be idiomatically correct Haskell. So I’m fine with the solution posted.

(I have GOT to learn Haskell.)

I did this in Ruby, and had a stupid error on my first try. The algorithm was right, but I was choosing the wrong array element because I used a bunch of one-character variable names and got mixed up. On second try, it worked:

def selection_sort(list)
  list.length.times do |starting_idx|
    smallest_idx = starting_idx
    smallest = list[starting_idx]

    starting_idx.upto(list.length - 1) do |current_idx|
      if list[current_idx] < smallest
        smallest_idx = current_idx
        smallest = list[current_idx]
      end
    end

    list[starting_idx], list[smallest_idx] = list[smallest_idx], list[starting_idx]
  end

  return list
end

Here’s an in-place JavaScript implementation. I haven’t tested it much, but it seems to work.

function selectionSort(arr) {
    for (var insertI = 0; insertI < arr.length - 1; insertI++) {
        var minI = insertI;

        for (var scanI = insertI + 1; scanI < arr.length; scanI++) {
            if (arr[scanI] < arr[minI]) {
                minI = scanI;
            }
        }

        var tmp = arr[insertI];
        arr[insertI] = arr[minI];
        arr[minI] = tmp;
    }
}

About 7 minutes to write, 3 typos fixed as I tried to compile it. Wrote it together with 3 dumb test vectors & it worked from the first try.

std::vector& ssort(std::vector& v)
{
typedef std::vector::iterator iter;

for (iter front = v.begin(); front != v.end(); ++front)
{
// find smalles element in the remaining part of the array
iter peek = front;
for (iter t = front + 1; t != v.end(); ++t)
if (*t < *peek)
peek = t;

// move smallest element to it's place
std::swap(*peek, *front);
}

return v;
}

Yuck. That site ate angle brackets off C++ stl vector.

Worked first time (except for syntax errors). About 6 minutes elapsed time.

smallest (int a[], int i, int j)
{
        int index = i;
        int low = a[i++];

        for (;i<=j; i++) {
                if (a[i] >= low)
                continue;
                low = a[i];
                index = i;
        }

        return index;
}

selectSort (int a[])
{
        int len = a.length;
        for (int i=0; i<a.length; i++) {

                int j = smallest(a,i,len-1);

                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
        }
        int sorted[] = a;
        return(sorted);
}

main ()
{
        int a[] = [23,-17,200,1024,999,7,6,5,-100];

        printf("Unsorted: %s\n",a.join(" "));

        a = selectSort(a);

        printf("Sorted: %s\n",a.join(" "));
}

I just noticed that all the solutions (including mine) iterating over elements a[0]..a[n], where n is the last element should really iterate to a[n-1]. This is because by the time a[n-1] is processed, a[n] must be in its correct place, so it does not need to be examined. Does this count as a bug, Mike?

In O’Caml. Didn’t take too long; though I struggled to figure out how to word my invariant(s). So I won’t be surprised if it fails…

(* selection sort *)

let sort arr =
let len = Array.length arr in
for i = 0 to len – 1 do
let min_pos = ref i in
for j = i+1 to len – 1 do
min_pos := if arr.(!min_pos) < arr.(j)
then !min_pos else j;
done;
let temp = arr.(i) in
arr.(i) <- arr.(!min_pos);
arr.(!min_pos) <- temp
done

Here’s a Clojure version; worked first time. Like rphan, I chose not to do the sort in place (partly) to avoid subtle errors. That’s also more in the spirit of Clojure — partly to avoid subtle errors.

(defn selmin [ns] (reduce #(if (<= %1 %2) %1 %2) ns))

(defn excluding [n ns]
  (let [[before after] (split-with #(not= n %) ns)]
    (concat before (rest after))))

(defn selsort [ns]
  (loop [sorted [], unsorted ns]
    (if (empty? unsorted)
      sorted
      (let [m (selmin unsorted)]
        (recur (conj sorted m), (excluding m unsorted))))))

Note there’s a core function ‘min’ that does the same thing as ‘selmin’. Tested with 0- to 4-length inputs, some including duplicated values.

Er, not quite true about Clojure ‘min’, which takes the minimum of its arguments, while my ‘selmin’ takes a single collection argument and returns the minimum of the collection. So (selmin coll) is equivalent to (apply min coll).
I knew you’d want to know…

Dang; boundary condition got me. In Java:

    public static int[] sort(int[] inArray) {
        if (inArray == null) {
            throw new IllegalArgumentException();
        }
        int[] outArray = new int[inArray.length];
        int curMax = Integer.MIN_VALUE;
        int curPos = 0;
        while(curPos < outArray.length) {
            int foundVal = Integer.MAX_VALUE;
            int count = 0;
            for (int curVal : inArray) {
                if (curVal < foundVal && curVal > curMax) {
                    foundVal = curVal;
                    count = 1;
                } else if (curVal == foundVal) {
                    count++;
                }
            }
            for(int j = curPos;j<curPos+count;j++) {
                outArray[j] = foundVal;
            }
            curMax = foundVal;
            curPos+=count;
        }
        return outArray;
    }

The bug is that Integer.MIN_VALUE will not be properly detected, as curVal > curMax, not >=. The fix was easy enough; I had to add an additional else if clause:

                } else if(curVal == Integer.MIN_VALUE && curPos == 0) {
                    foundVal = curVal;
                    count= 1;
                }

I can post my test suite, if desired. Mostly just checking 0 len, 1 len with min and max int, multiple min and max int, multiple other digits, etc.

In-place sort array of 32-bit integers, x86 assembler. Had one bug – the off by one error I mentioned in a previous post.

;————————————–
; assume: esi = *a, ecx = sizeof(a)
;————————————–
cmp ecx, 2
jl _l3
dec ecx
mov edi, esi
_l1: mov ebx, ecx
mov eax, [edi]
mov edx, edi
_l2: add esi, 4
cmp eax, [esi]
jl @F
mov eax, [esi]
mov edx, esi
@@: dec ebx
jnz _l2
cmp edx, edi
je @F
push [edi]
mov [edx], eax
pop eax
mov [edi], eax
@@: add edi, 4
mov esi, edi
dec ecx
jnz _l1
_l3:

My first language is Java, so I wrote the following code first:

public class SelectionSort {

    public static int[] sort(int[] arr) {

        // handle null input
        if(arr == null)
            return null;

        // fill index i with the correct value
        for(int i=0; i<arr.length-1; i++) {

            // find min value in arr[i..]
            int minIndex = i;
            for(int j=i; j<arr.length; j++)
                if(arr[j] < arr[minIndex])
                    minIndex=j;

            // if different, do a swap
            if(minIndex != i) {
                int tmp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = tmp;
            }
        }

        return arr;
    }

}

But I’m also learning Haskell, so I gave that a shot as well. It’s astounding how small the Haskell code is compared to the Java, and I even wrote my own min function! The delete might be too powerful: it removes the first occurrence of an item that it can find in a list.

import Data.List

ssort :: [Int] -> [Int]
ssort [] = []
ssort xs = smallest : ssort (delete smallest xs)
           where min a b = if a < b then a else b
                 smallest = (foldl1 min xs)

Both were written first and then tested. They seem to work, but I haven’t done any formal analysis to prove that!

Argh; after quickly looking at the other solutions, I realized how terrible mine was. Here’s a Java in-place solution that I got right in one try. I had skimmed over the other solutions here first, so it’s not a fair submission.

    public static void sortInPlace(int[] inArray) {
        if (inArray == null) {
            throw new IllegalArgumentException();
        }
        for(int start = 0; start < inArray.length;start++) {
            int val = inArray[start];
            int swapPos = start;
            for(int i = start+1;i<inArray.length;i++) {
                if(inArray[i] < val) {
                    val = inArray[i];
                    swapPos = i;
                }
            }
            int temp = inArray[start];
            inArray[start] = inArray[swapPos];
            inArray[swapPos] = temp;
        }
    }

Took much longer to write the tests (which I did after finishing) than to write the function (which only took 2-3 minutes). C++.

template<class Iter, class Cmp>
void selection_sort(Iter begin, Iter const end, Cmp lt) {
  for (; begin != end; ++begin) {
    Iter smallest = std::min_element(begin, end, lt);
    if (smallest != begin) {
      using std::swap;
      swap(*smallest, *begin);
    }
  }
}

Code includes test cases which I did not run until I was satisfied that the program was correct. It is, at least according to my test cases, which are probably far from complete. Code works, 13 LOC Python, ~5 minutes.

def selsort(array):
    """
    >>> selsort([1, 2, 3])
    [1, 2, 3]
    >>> selsort([3, 2, 1])
    [1, 2, 3]
    >>> selsort([])
    []
    >>> selsort([1])
    [1]
    >>> selsort([1, 1, 1])
    [1, 1, 1]
    >>> selsort([1, 2, -1])
    [-1, 1, 2]
    >>> selsort([1, 2, 9999999, 3])
    [1, 2, 3, 9999999]
    """

    # short-circuit for non-sortable arrays
    if len(array) <= 1:
        return array

    # invariant: by the end of each iteration of
    # loop on i, array[i] is greater or equal to
    # array [i-1]
    for i in range(len(array)):
        s = i
        lowest = array[i]

        # invariant: by the end of each iteration
        # of loop on j, s is the index of the least
        # valued element in range [i+1:j]
        for j in range(i+1, len(array)):
            if array[j] < array[i] and array[j] < lowest:
                s = j

        # swap elements at i and s
        temp = array[i]
        array[i] = array[s]
        array[s] = temp

    return array

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Took about 30 minutes and, since I am at work and so without facilities, I wrote it in Notepad and I haven’t even compiled it, so I am fully braced for failure. Anyway, here goes:

void selection_sort(int a[], const int size) {
  int lowest;
  int upper;
  int index;
  int temp;

  for (upper = size-1; upper > 0; upper--) {
    lowest = 0;
    for (index = 1; index < upper; index++) {
      if (a[index] < a[lowest]) {
        lowest = index;
      }
    }
    if (lowest != upper) {
      temp = a[upper];
      a[upper] = a[lowest];
      a[lowest] = temp;
    }
  }
}

Quick Python version. No type checking as it should be able to support anything that can be made into a list using list().

def sort(inlist):
	""" Returns sorted version of inlist
		Input:
			inlist - a list object
		Output:
			Sorted copy of inlist.  inlist remains untouched.
		Notes:
		Array operations may throw exceptions.  This should be
		able to sort anything that is iterable and supports
		array access.
	"""
	result = list(inlist)
	sz = len(inlist)
	for x in range(0,sz):
		for y in range(x+1,sz):
			if (result[x] > result[y]):
				tmp = result[x]
				result[x] = result[y]
				result[y] = tmp
	return result

Having now looked at some of the others I’ve realised that I misunderstood “stash it down at the bottom of the array” to be at the highest index rather than the lowest, so I have rewritten accordingly and also renamed “lowest” as “smallest” to avoid confusion with “lower”.

Still not compiled, so for all I know it doesn’t even run, but hey, ho, what can you do?

void selection_sort(int a[], const int size) {
  int smallest;
  int upper = size - 1;
  int lower;
  int index;
  int temp;

  for (lower = 0; lower <= upper; lower++) {
    smallest = lower;
    for (index = lower + 1; index <= upper; index++) {
      if (a[index] < a[smallest]) {
        smallest = index;
      }
    }
    if (smallest != lower) {
      temp = a[lower];
      a[lower] = a[smallest];
      a[smallest] = temp;
    }
  }
}

Count this as a fail, because I mixed up i and j in the swap the first time around, and had to try it out a few times to catch it.

def selection_sort(l):
	for i in range(len(l)):
		min_idx = i
		for j in range(i + 1, len(l)):
			if l[min_idx] > l[j]:
				min_idx = j
		l[min_idx], l[i] = l[i], l[min_idx]
	return l

I didn’t try to do exhaustive testing, just relied on random numbers for a range of array sizes. The testing could easily be harder than the algorithm itself for this kind of challenge. I was pretty confident of my code before I ran it and all tests passed, but I don’t discount the possibility that I missed an edge condition. Python source:

def selection_sort(array):
    if len(array) <= 1: return array
    for slot in range(0, len(array) - 1):
        min_index = slot
        for i in range(slot + 1, len(array)):
            if array[i] < array[min_index]:
                min_index = i
        if min_index != slot:
            array[min_index], array[slot] = array[slot], array[min_index]
    return array

import random

def test_selection_sort():
    for length in range(0, 1000):
        array = []
        for i in range(0, length):
            array.append(random.randint(-1000, 1000))
        if selection_sort(array[:]) != sorted(array):
            raise AssertionError()
        array.sort()
        if selection_sort(array[:]) != array:
            raise AssertionError()
        print "passed: ", length

An in-place sort in Ruby. I favoured simplicity over efficiency, and testing was very brief.

def selection_sort(a)
  (0...a.size).each do |i|
    m = (i...a.size).reduce { |m, j| a[j] < a[m] ? j : m }
    a[i], a[m] = a[m], a[i]
  end
  a
end

@ Arild/Mike Taylor/Corey Porter:

Okay, I cry “uncle” at Corey’s haskell solution. Is this readable once you’re used to the Haskell syntax? and what is the run-time for Corey’s implementation? (I have Real World Haskell, but it’s a hard slog)

Here’s mine, with pre-conditions, post-conditions, and invariants specified. I was really lazy, and haven’t even tested that it compiles, but fingers crossed!

BTW, it’s in Java

public void sort(a) {
   // PRE- a[0...n] unsorted
   // INV: a[0...k] <= a[k+1...n]
   // POST: a[0...k] sorted

  int n = a.length -1; 
  int k = -1;
  while(k<n) {
    k++;  
    int j = k;
    while(j < n) {    
      j++;
      if(a[j] < a[k]) { // ensures invariant remains true
	swap(a, j, k);
      }
    }
  }
}

public void swap(a, x, y) {
  int oldax = a[x];
  a[x] = a[y];
  a[y] = oldax;
}

Nope, didn’t compile because I forgot types in the method signature. Again, compiling

public void sort(int[] a) {
  // PRE- a[0...n] unsorted
  // INV: a[0...k] <= a[k+1...n]
  // POST: a[0...k] sorted

  int n = a.length -1;
  int k = -1;
  while(k<n) {
    k++;  
    int j = k;
    while(j < n) {    
      j++;
      if(a[j] < a[k]) {
	swap(a, j, k);
      }
    }
  }
}

public void swap(int[] a, int x, int y) {
  int oldax = a[x];
  a[x] = a[y];
  a[y] = oldax;
}

I made a really stupid error on my first try, but I basically had it right. I think this exercise was actually quite a bit easier than the binary search bit.
This is my corrected version in C#:

        public static int[] SelectionSort(int[] array)
        {
            int upperIndex = array.Length - 1;

            while (upperIndex > 0)
            {
                int lowerValue = array[0];
                int lowerIndex = 0;

                for (int i = 1; i < upperIndex; i++)
                {
                    if (lowerValue > array[i])
                    {
                        lowerValue = array[i];
                        lowerIndex = i;
                    }
                }

                if (lowerValue < array[upperIndex])
                {
                    int upperValue = array[upperIndex];

                    array.SetValue(upperValue, lowerIndex);
                    array.SetValue(lowerValue, upperIndex);
                }

                upperIndex--;
            }
            
            return array;
        }

This is the original, erroneous part of the code (which retains the value of lowerValue and lowerIndex from the last run of the loop, and so fails):

            int lowerValue = array[0];
            int lowerIndex = 0;

            while (upperIndex > 0)
            {
                for (int i = 0; i < upperIndex; i++)
                {etc.

int i_next_smallest(const int *s, const int pos, const int length)
{
        int min = INT_MAX, min_pos = 0, i = pos;
        for (; i < length; i++)
        {
                if (s[i] <= min)
                {
                        min = s[i];
                        min_pos = i;
                }
        }

        return min_pos;
}

void i_swap(int *s, const int a, const int b)
{
        int temp = s[a];
        s[a] = s[b];
        s[b] = temp;
}

void i_sort(int *s, const int size)
{
        int min_pos, i = 0;

        while(i < size)
        {
                // get smallest number from the remaining array
                min_pos = i_next_smallest(s,i,size);

                // switch positions
                if (i != min_pos)
                {
                        i_swap(s, i, min_pos);
                }

                i++;
        }
}

time: about 20 min.
didn’t run it before submitting, tried it now – seems to work with empty array, 1 element array, random content, reverse sorted and all same values. any other testcases I missed?

JavaScript, failed. The bug has nothing to do with algorithm though, I got “splice” syntax wrong. No amount of thinking about border conditions and invariants could fix this. I don’t believe in these things at all, you have to think, that’s all. You have to visualize the algorithm.

function selectionSort(arr) {
  for (var len = arr.length; len>0; len--) {
    for (var i=0, indexOfMin=0; i<len; i++)
      if (arr[i] < arr[indexOfMin]) indexOfMin = i
    arr.push(arr.splice(arr, indexOfMin, 1).pop())
  }
  return arr
}

Less than 10 minutes in C99. The code doesn’t handle 0 sized arrays (as my tests bore out) but it works on arrays of 1 or more elements.

void selectsort(int *list,const size_t listsize)
{
  for (size_t i = 0 ; i < listsize - 1 ; i++)
  {
    for (size_t j = i + 1 ; j < listsize ; j++)
    {
      assert(i <  j);
      assert(j >  i);
      assert(i != j);
      
      assert(i < listsize - 1);
      assert(j < listsize);

      if (list[j] < list[i])
      {
        int tmp = list[i];
        list[i] = list[j];
        list[j] = tmp;
      
        assert(list[i] < list[j]);
      }
    }  
  }    
}

Personally, I don’t consider a 0-element array as being valid, but that’s me …

Well it’s Perl again, I know and it works. The key phrase I think here is ‘stash’, in my case I swap the current first value with the lowest level value in the array and then move up the first value pointer.

sub select_sort {
	my $array = shift;

	for my $start (0..scalar(@{$array})-1 ) {

		my $min = $array->[$start];
		my $idx = $start;
				
		for my $i ( $start..scalar(@{$array})-1 ) {
			if ( $min > $array->[$i] ) { 
				$idx = $i; 
				$min = $array->[$i]; 
			}
		}
	
		my $val = $array->[$idx];
		$array->[$idx] = $array->[$start];
		$array->[$start] = $val;
	
	}
	
	return $array;
}

Also… the first time I thought I was finished I foolishly had missed out line 12, which is kind of one of the more important ones in the whole thing. So it’s a failure due to sloppiness.

And possibly due to terrible code as well.

Perl.

use strict; 
use warnings;

sub selSort
{
	my $a = shift;

	return if !@$a;

	my $min = 0;
	for my $i (1 .. @$a-1)
	{
		$min = $i if $a->[$i] < $a->[$min];
	}

	return (splice(@$a, $min, 1), selSort($a));
}

I abandoned last night and tried again today, and not because the problem but my lack of knowledge with Perl arrays.

So I failed.

Sean Conner wrote:

Personally, I don’t consider a 0-element array as being valid, but that’s me.

A couple of people said this in the binary-search exercise, too. I find it utterly bewildering. Of course an empty set is a perfectly good set. It’s just as valid a set as an empty string is a valid string: how would we feel about a strlen() function that didn’t work on empty strings?

Or think about the ls command that lists files in the working directory, sorted: what would we think of such a program if it didn’t work in empty directories, due to the sort routine not working on empty arrays?

FORTRAN and C: http://pastebay.com/99468

I was not really clear on the concept and added a few enhancements to the C version, and for a while it appeared to be O(n), but then it became slower than the FORTRAN version.

The C version was going to work but then I changed this:

if (…) continue;

to this

if (…) continue;
continue;

so it didn’t work the first time.

The FORTRAN version worked the first time, but by then I had looked at some of the other postings so it doesn’t count, then I broke it, now it’s working again.

Oh yeah, that last post (http://pastebay.com/99468) includes a test harness.

fixed a comment typo: new URL:

http://pastebay.com/99470

Brian wrote:

I added a few enhancements to the C version, and for a while it appeared to be O(n),

Brian, if you write an O(n) search routine, then go straight to the Nobel Prize committee!

:-)

@Mike: yeah, tell me about it.

No testing, just thinking. Ran perfectly first time. Then ran again with various types of arrays, empty, etc. Took about an hour. Each draft produced another problem in my mind.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int ints[] = {4,3,7,2,23,444,53,23,6,-1,0};
	int intsSize = sizeof(ints)/sizeof(int);
	int buffer, count, shuffleCount;

	for (count=1; count < intsSize; count++) {
		if (ints[count] < ints[0]) {
			buffer = ints[count];
			for (shuffleCount = count; shuffleCount > 0; shuffleCount--) {
				ints[shuffleCount] = ints[shuffleCount - 1];
			}
			ints[0] = buffer;
		}
		else {
			while (ints[count] < ints[count-1]) {
				buffer = ints[count-1];
				ints[count-1] = ints[count];
				ints[count] = buffer;
				count--;
			}
		}
	}

	for (count=0; count < intsSize; count++) {
		printf("%d ", ints[count]);
	}
	printf("\n");

	return 0;
}

Seems to be working on the first try.
Tested on empty, one element, sorted, reverse sorted and random arrays (checking against library’s qsort).

[/code]
void ss(int *array, const int size){
int current;

for(current = 0; current < size; current++){
int pos_min, i;
pos_min = current;
for(i=current+1; i<size; i++){
if(array[i] < array[pos_min]){
pos_min = i;
}
}

if(pos_min != current){
int min = array[pos_min];
array[pos_min] = array[current];
array[current] = min;
}
}
}
[/code]

Sorry about that. Second try:

void ss(int *array, const int size){
int current;

for(current = 0; current < size; current++){
int pos_min, i;
pos_min = current;
for(i=current+1; i<size; i++){
if(array[i] < array[pos_min]){
pos_min = i;
}
}

if(pos_min != current){
int min = array[pos_min];
array[pos_min] = array[current];
array[current] = min;
}
}
}

Holy s***…

void ss(int *array, const int size){
    int current;

    for(current = 0; current < size; current++){
        int pos_min, i;
        pos_min = current;
        for(i=current+1; i<size; i++){
            if(array[i] < array[pos_min]){
                pos_min = i;
            }
        }

        if(pos_min != current){
            int min = array[pos_min];
            array[pos_min] = array[current];
            array[current] = min;
        }
    }
}

It looks like the blog is rejecting my comments when I use a certain email address. I’m trying another one now, so if the other post shows up eventually, please excuse the double post.

Wrote my version in Haskell and it worked perfectly the first time. No testing.

http://pastie.org/969081

this one’s in php… on the first try, it correctly sorted this one: 4, 2, 15, -6, -50, 0, 0, 4, 2, 13, -23, -23, -23, 66, 6

function selection_sort($tosort) {
	if(!is_array($tosort))
		return false;
	if(count($tosort)==0)
		return $tosort;
	
	$elements = count($tosort);
	$result = array();
	
	while(count($result) < $elements) {
		$minkey = 0;
		foreach($tosort as $key=>$value) 
			if($value < $tosort[$minkey]) 
				$minkey = $key;
		$result = array_merge($result, array_splice($tosort, $minkey, 1));
	}	
	
	return $result;
}

void selectionsort(int *a, int len)
{
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			if (a[j] < a[i]) {
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
}

Python: http://pastebin.com/TzLZcHyS (essentially the same as “rphan”, but mine is bit uglier)

Worked on first try without any bugs. Seems to work on empty arrays, duplicates, random arrays.

Wrote it in a few minutes, then I carefully walked myself through the code, before I did some informal reasoning about the invariants and bounds of the two loops.
(Invariants: all values in ret_arr is always smaller than the ones in array, and min[1] is smaller than all values previously iterated over in the current run of the for-loop. “Boundness”: the while loop reduces array with each run, and the for loop iterates over array without adding anything to the list it iterates over.)

I do have to admit that I didn’t consciously consider the case of the empty array. Maybe I’m just used to writing loops that terminate on empty array in python. Not very idiomatic python though, and there’s some weirdness that i blame on lack of sleep.

(Great challenge, even though it wasn’t that hard. Keep up the good work and the interesting articles!)

Here’s the algorithm. Seems I got it right on the first try, but I must admin I spent more time on getting my invariants right than on coding out the algorithm. This one’s pretty simple, and I’m not sure the invariants helped me a lot here…

void selection_sort(int array[], int n) {
    /* PRE: true */

    /* INV0: forall i <= j < k: array[i] <= array[j] */
    /* INV1: forall k <= i < n: array[k] <= array[i] */
    for (int k = 0; k < n; k++) {
        int min_idx = k;

        /* INV: forall k <= j < i: array[min_idx] <= array[j] */
        for (int i = k; i < n; i++) {
            if (array[i] < array[min_idx]) min_idx = i;
        }
        /* POST: forall k <= j < n: array[min_idx] <= array[j] */

        int h = array[k];
        array[k] = array[min_idx];
        array[min_idx] = h;
    }
    /* POST: forall i <= j < n: array[i] <= array[j] */
}

Seemed to run fine first go against an pretty simple test set.

void sort(int v[], int len)
{
    int i, j, m, t;

    for (i = 0; i < len; i++)
    {
        m = i;
        for (j = (i + 1); j < len; j++)
            if (v[j] < v[m])
                m = j;

        t = v[i];
        v[i] = v[m];
        v[m] = t;
    }
}

I used C#. After spending a few minutes planning on paper, I got to it. Wrote the function, read it through a few times, then tested it. I’m happy to report that it worked first time :)

        static void SelectionSort(ref int[] array)
        {
            long ubound = array.LongLength - 1;
            long position;
            long loop1 = 0;
            long loop2;
            int minval;

            while (loop1 <= ubound)
            {
                position = loop1;
                minval = array[position];
                loop2 = loop1;
                while (loop2 <= ubound)
                {
                    if (array[loop2] < minval)
                    {
                        position = loop2;
                        minval = array[position];
                    }
                    loop2++;
                }

                if (position > loop1)
                {
                    array[position] = array[loop1];
                    array[loop1] = minval;
                }
                loop1++;
            }
        }

This was a very interesting exercise :)

My version is in OCaml, whic I thought would be useful. I did not do intensive testing once it compiled, even if it took me a lot of time (partly because I am an OCaml beginner).
Anyway, I know my version does not handle long list because one of my function is not tail-recursive, but as I discovered that during testing, it was too late :).

(* Min of an list
 * pre: the original list is not empty
 * post: the returned value is the minimum of the list 
 *)
let rec min lst =
    match lst with
    [] -> Pervasives.max_int
    | h ::  sublst ->
        let m = min (sublst) in
        if h < m then
            h
        else
            m
;;
(* Strip a given value from a list
 * pre: the value exists in the list, and the list is not empty
 * post: returns the original list with the first occurence of value
 * stripped, plus the value itself
 *)
let rec strip value lst =
    let h = List.hd lst in
    let sublst = List.tl lst in
    if h = value then
        (sublst, value)
    else
        let (tail, tval) = strip value sublst in
        (h :: tail, tval)
;;
(* The sorting itself
 * pre: none
 * post: the list is hopefully sorted
 *)
let rec sel_sort lst =
    match lst with
    [] -> []
    | _ ->
        let (todo, pcssed) = strip (min lst) lst in
        (sel_sort todo) @ [pcssed]
;;
(* Read the list of int from stdin
 * pre: none
 * post: none
 *)
let rec read_lst lst =
    try
        let i = Pervasives.read_int () in
        read_lst (lst @ [i])
    with
    End_of_file -> lst
;;
(* Main routine
 *)
let main =
    let lst = read_lst [] in
    let sorted = sel_sort lst in
    List.iter (Printf.printf "%i\n") sorted
;;

After looking at what a few other people did, I changed the line:

loop2 = loop1;

to

loop2 = loop1 + 1;

No need to test a value against itself. One optimisation so far.

Tried in Go. infinite loop because of a typo (j/i). it’s inefficient but should work for random, sorted, empty lists ..

Python – untested

def selection(a):
    length = len(a)
    b = []
    while length:
        min_loc = 0
        for i, ai in enumerate(a[1:]):
            if ai < a[min_loc]:
                min_loc = i
        b.append(a.pop(min_loc))        
        length -= 1
    return b

I think Vince has a good point about the first loop having to only go as far as the second to last element in the array. Made that change in my code, it still passes all the tests, but now in one less iteration. That brings my optimisations up to two :)

@Vince, I don’t think that should count as a bug. The algorithm still does exactly what it’s supposed to. I’d call it an optimisation.

Well I completely failed on my first try, doh!
I hope this one is better.

void selectionsort2(int *a, int len)
{
	for(int i = 0; i < len-1; i++) {
		int smallest = i;
		for (int j = i + 1; j < len; j++) {
			if ( a[j] < a[smallest]) {
				smallest = j;
			}
		}

		if (smallest > i) {
			int temp = a[smallest];
			a[smallest] = a[i];
			a[i] = temp;
		}
	}
}

In-place update seemed easiest, and so:

def selsort(array):
    alen = len(array)
    remi = 1
    while remi < alen:
        lowi = remi - 1
        minv = array[lowi]
        mini = lowi
        for i in xrange(remi, alen):
            val = array[i]
            if val < minv:
                minv, mini = val, i
        array[lowi], array[mini] = array[mini], array[lowi]
        remi += 1
    return array

Worked as far as I can tell.

In Perl:

#!/usr/bin/perl -w

use strict;
use warnings;

sub selection_sort {
  return () if @_ == 0;

  my @result;

  for (0 .. $#_) {
    my $min = $_[0];
    my $index = 0;

    for (my $i = 1; $i < @_; $i++) {
      my $curr = $_[$i];
      if ($curr < $min) {
        $min = $curr;
        $index = $i;
      }
    }

    push @result, splice @_, $index, 1;
  }

  return @result;
}

This took about 8–10 minutes to write and it seemed to run correctly on first blush, which is definitely not what I expected, since I am very much the sort of person who puts out junk as a first draft then carefully refines it into something slightly less broken.

It also seems okay according to the limited test harness I wrote after the fact (which took me another 10 minutes, yeesh):

sub test_sort {
  my $mine = join " ", selection_sort(@_);
  my $ref = join " ", sort { $a <=> $b } @_;
  print "$mine - " . ($mine eq $ref ? "pass" : "fail") . "\n";
}

test_sort(1, 6, 3488, 3478, 3489, 235, 110);
test_sort();
test_sort(-2000000, 0, 2000000);
test_sort(-934838, 39389, 57982374, 908213, -2381923);
test_sort(1, 6, 3488, 3478, 3489, 235, 110, 1, 6, 3488, 3478, 3489, 235, 110);

I haven’t tried with anything but integers.

I tried to solve this using Haskell (a language I’m trying to learn, so probably not the best Haskell-ness in my code). I kind of think it should work, but I’m not sure.

selectionsort [] = []
selectionsort (a:as) = selhelper [] a as

selhelper [] min [] = min:[]
selhelper (a:as) min [] = min : selhelper [] a as
selhelper pre min (a:as)
| min <= a = selhelper (a:pre) min as
| otherwise = selhelper (min:pre) a as
[\source]

my Python naive implementation:

# Assume l is an integer list.
def insertion_sort(l):
    result = []
    length = len(l)
    start = 0

    # Invariants:
    # 0 --> start values are sorted.
    # 0 --> start - 1 values are inferior or equal to l[start - 1].
    # start --> length - 1 values are superior or equal to l[start - 1]
    while start < length:

        # Find sublist minimum index.
        min_index = start
        min_value = l[min_index]

        i = start
        while i < length:
            if l[i] < min_value:
                min_value = l[i]
                min_index = i
            i += 1

        # Swap found index.
        l[start], l[min_index] = l[min_index], l[start]

        start += 1

    return l

I failed the exercice, as I wrote

l[start], l[i] = l[i], l[start]

instead of

l[start], l[min_index] = l[min_index], l[start]

when it ran it the first time.

For the record: I spent about 15 minutes on it. I’m not familiar with invariants.

The code only was run with:

print insertion_sort([])
print insertion_sort([1])
print insertion_sort([1, 2, 3, 4, 5])
print insertion_sort([1, 2, 4, 3, 5])
print insertion_sort([5, 4, 3, 2, 1])

I’ve posted a few times on this blog using my real name, but I think that receiving fame or shame for your code might bias the result of the experiment, so I encourage everyone to post anonymously.

My test case consisted of 1000 runs each of arrays of sizes up to 1000 items. I used the result of the GCC standard C library qsort as a reference, and as a sort of double check for the integer comparison routine I supplied to the qsort I also checked so each item in both arrays was not smaller than the previous.

I had 1 typo, but on the second compile the code passed all tests, so I’m confident the implementation is bug free:

void ssort(int* const data, const unsigned int size)
{
	int temp;
	unsigned int first, index, n;

	if(size >= 2)
	{
		for(first = 0; first <= size-2; first++)
		{
			index = first;

			for(n = first+1; n <= size-1; n++)
				if(data[n] < data[index])
					index = n;

			temp = data[first];
			data[first] = data[index];
			data[index] = temp;
		}
	}

}

Java. Seemed to work.

    static void sort(int ra[])
    {
    int i, j, m, t;

        for (i = 0; i < ra.length - 1; i++) {
            m = i;
            for (j = i + 1; j < ra.length; j++) if (ra[j] < ra[m]) m = j;
            if (i != m) {
                t = ra[m];
                ra[m] = ra[i];
                ra[i] = t;
            }
        }
    }

Written in C with VCC extensions, see [link]http://vcc.codeplex.com[/link].

#include <vcc.h>

void ssort(int *a, unsigned int len)
  writes(array_range(a, len)) // attepting to verify a call with a NULL reference would fail
  ensures(forall (unsigned int n, m; n < m && m < len ==> a[n] <= a[m])) // sorted when we leave the function
{
  unsigned int i,j,k;
  int tmp;
  for (i = 0; i < len; i++) 
    invariant(forall (unsigned int n, m; n < m && m < i ==> a[n] <= a[m]))             
    // sorted up to i
    invariant(forall (unsigned int n, m; n < i && i <= m && m < len ==> a[n] <= a[m])) 
    // only larger values after i
  {
    for (j = i, k = i; j < len; j++) 
      invariant(i <= j && j <= len && i <= k && k < len)
      invariant(forall (unsigned int n; i <= n && n < j ==> a[k] <= a[n])) 
      // a[k] is the smallest value from a[i..j]
    {
      if (a[j] < a[k]) k = j;
    }
    
    tmp = a[i];
    a[i] = a[k];
    a[k] = tmp;
  }
}

Never ran it but the verifier says it works so it has to be correct :-)

* wrote it in emacs, without the doctests, about 10 minutes to be happy

* ran it once to check syntax… OK

* tested on paper for with zero, one, two, and three elements … fixed one bug (the inner range was too short by one, because i lazily typed out that loop with the same upper bound as the outer loop). Also made a trivial optimization (j can starts at i+1, although it works fine if it starts at i).

* wrote doctests, ran them, all passed.

"""

>>> selection_sort([])
[]

>>> selection_sort([5])
[5]

>>> selection_sort([1, 5])
[1, 5]

>>> selection_sort([5, 1])
[1, 5]

>>> selection_sort([0, 5, 0, 5, 5, 0])
[0, 0, 0, 5, 5, 5]

>>> selection_sort([5, -4, 88, 3, 999, -2000, 0])
[-2000, -4, 0, 3, 5, 88, 999]

>>> selection_sort(['green', 'eggs', 'and', 'ham'])
['and', 'eggs', 'green', 'ham']

And for good measure some fuzzy testing:

>>> import random
>>> def make_random(len):
...     result = [0] * len
...     for i in xrange(len):
...         # using ints so it's fairly likely there will be dupes
...         result[i] = random.randint(-100, 100)
...     return result
>>>
>>> for i in range(1000):
...     input = make_random(i)
...     # sorted makes a copy; mine is in-place, so call sorted first.
...     assert sorted(input) == selection_sort(input)
>>>
"""

def selection_sort(alist):
    for i in xrange(len(alist) - 1):
        sel = i
        for j in xrange(i + 1, len(alist)):
            # rules say "using min() is borderline", so let's not.
            sel = sel if (alist[sel] <= alist[j]) else j
        alist[i], alist[sel] = alist[sel], alist[i]
    return alist


if __name__ == '__main__':
    import doctest
    print doctest.testmod()

5 minutes, works without bugs for empty sets, sets with duplicate entries, reversed sets, ordered sets, partly ordered sets. simple recursive algorithm:

def selection_sort(l):
    if len(l) == 0:
        return l

    min_val = l[0]
    min_i = 0
    for i in range(1, len(l)):
        if l[i] < min_val:
            min_val = l[i]
            min_i = i

    return [l[min_i]] + selection_sort(l[:min_i] + l[min_i+1:])

Which reminds me. If you find a bug by testing on paper, does that count as success or failure? :)

Paul Winkler asked:

Which reminds me. If you find a bug by testing on paper, does that count as success or failure? :)

That’s success, because you found the bug by thinking about the code rather than just throwing it at the computer and seeing whether it stuck. (That’s assuming that when you did run it, it passed the tests, of course!)

Let me preface this by saying, “you bastard!” You can’t just post challenges like this, you’re ruining lives! I was supposed to be meeting friends in town. I’ll have to make up some excuse now. So I’ve mentally stepped through my code and I am very confident that it is correct. I haven’t tested it. Here’s hoping it’s correct. It took me 15 minutes. Bring on the shame! Oh, the shame!

sort :: Ord a => [a] -> [a]
sort [] = []
sort xs' = take_or_swap Nothing xs' [] where
    take_or_swap Nothing  []     _  = []
    take_or_swap (Just a) []     ys = take_or_swap Nothing ys [] ++ [a]
    take_or_swap Nothing  (x:xs) ys = take_or_swap (Just x) xs ys
    take_or_swap (Just a) (x:xs) ys | a < x     = take_or_swap (Just a) xs (x:ys)
                                    | otherwise = take_or_swap (Just x) xs (a:ys)

(Before anyone says “that’s a list, not an array”, just like last time, I think the algorithm’s the same. And I don’t know Haskell arrays, I don’t think it would be representative for me to use a library I’m not familiar with in this challenge.)

Bahaha, I just tested it. Perfection! *Cackles maniacally* Now I’m going out for coffee. Ciao! Not this time, Mike! Stick to reviewing Buffy. ;-P

Didn’t work the first time because I didn’t follow the invariant I wrote. I said I x(i) has to be the min value. If not then find the min value and swap it with x(i) so that x(i) has the min value. Except the code I wrote to find the min value was incorrect. (I’m doing in-place. So I did x(j) < x(i). Instead of the correct x(j) < x(k) where k is the index to the last min value found.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <ctime>
#include <cstdlib>
#include <cmath>

using namespace std;

//hackish isSorted test.
bool isSorted(int x[], size_t L)
{
for(size_t i=0; i < L-1; i++)
{
if(x[i] > x[i+1])
return false;
}
return true;
}

void printArray(int x[], size_t L)
{
cout << "{";
for(size_t i=0; i < L-1; ++i)
{
cout << x[i] << ",";
}
cout << x[L-1] << "}" << endl;
}

/**
*This function will sort an array of ints,in place, and in ascending order.
*
* I while C body not C and I
*Really informal invariant.
*
* Let i be the current index. Let j = i+1. The following invariances must ALL hold (AND relation):
* let x be the array. Let x(i) denote the value of array at i.
* I1) i <= L.
* I2) j <= L.
* I3) k < L.
* SO that (informally):
(i <= L AND j <= L AND k < L) while( i < L and j < L and k < L) outer loop, inner loop (i = L and j = L and k < L)

* Very very informal
*
* I4) x(i) must contain the minimum value of the array. If not, then find the minimum value in rest of the array and swap that with x(i), so that x(i) contain the minimum value of the array.
*/
void SelectionSort(int x[], size_t L)
{
assert(x!=0 && "Null array.");
assert(L>0 && "Array length is 0.");
for(size_t i=0; i < L; ++i)
{
size_t k = i; //k is used to remember the index for the min. value.
for(size_t j=i+1; j < L; ++j)
{
if(x[j] < x[k]) //Did we find a new min. value?
{
k = j; //remember where we found this.
}
}
if(k>i) //we found a new min. value.
swap(x[i],x[k]); //swap them. I4 says x(i) must contain the min. value. Which is true at this pointer.
}
}

int testSort(int x [], size_t L)
{
SelectionSort(x,L);
if(isSorted(x,L))
{
cout << "Sorted!" << endl;
return 1;
}
else
{
cout << "Not sorted!" << endl;
return 0;
}
}
static const int LO_R = -10000;
static const int HI_R = 10000;
static const int RANGE = HI_R-LO_R;
int RandomInt()
{
return LO_R + int(RANGE*rand()/(RAND_MAX + 1.0)); //Not good rand()!
}

void fillRandArray(int x[], size_t L)
{
for(size_t i = 0; i < L; ++i)
{
x[i] = RandomInt();
}
}

static const size_t RANDOM_COUNT = 20000;
int main(int argc, char* argv[])
{
srand(unsigned(time(0)));
int maxLimit = numeric_limits<int>::max();
int minLimit = numeric_limits<int>::min();
int TA [] = {6,5,4,3,2,1,0,-1};
int TA1 [] = {maxLimit,0,-23,minLimit};
int TA2 [] = {minLimit};
int TA3 [] = {0,0,0,0,0,0,0};
int THE_RANDOM_BABY[RANDOM_COUNT];

int numPassed = 0;
size_t L = size_t(sizeof(TA) / sizeof(int));
numPassed += testSort(TA,L);
L = size_t(sizeof(TA1) / sizeof(int));
numPassed += testSort(TA1,L);
L = size_t(sizeof(TA2) / sizeof(int));
numPassed += testSort(TA2,L);
L = size_t(sizeof(TA3) / sizeof(int));
numPassed += testSort(TA3,L);

for(int i=0; i < 6; i++)
{
fillRandArray(THE_RANDOM_BABY,RANDOM_COUNT);
numPassed += testSort(THE_RANDOM_BABY,RANDOM_COUNT);
}
cout << "Total passed should be 10! Passed: " << numPassed << endl;
return 0;
}

Non-recursive, a bit verbose but seems to work.

import sys

def find_min(array):
    """
    Return the min element and index of same in an array of integers.
    """
    assert(isinstance(array, list))
    assert(len(array) > 0)
    assert(isinstance(array[0], int))

    cur_min = sys.maxint
    cur_idx = len(array) + 1

    for x in range(0, len(array)):
        if array[x] < cur_min:
            cur_min = array[x]
            cur_idx = x

    return cur_min, cur_idx

def selection_sort(array):
    """
    Do selection sort, returning a (new) sorted array.
    Assumes input is an array of integers.
    """

    assert(isinstance(array, list))
    assert(len(array) > 0)
    assert(isinstance(array[0], int))

    output = []

    while len(array) > 0:
        val, idx = find_min(array)
        output.append(val)
        del(array[idx])

    return output

For fun, I decided to do another implementation in perl. This one is inline and as terse as I could make it (also for fun). Though I’m sure some super perl monk could probably write it with even less code.

It was scary running this for the first time, but luckily everything seemed to work!

sub ssort {
    while( $i++ < $#_ ) {
        my $m = $i - 1;
        for( $i .. $#_ ) {
            $m = $_ if $_[$_] < $_[$m];
        }
        $t = $_[$i - 1];
        $_[$i - 1] = $_[$m];
        $_[$m] = $t;
    }
}

One bug found in test suite – boundary condition for input only holding MAXINT. Sigh.

@Paul Hubbard: I tend to think you should either sort the input array in-place, or leave it alone. Deleting all elements is a rather surprising side effect :)

Seems to work though, except that you deliberately don’t handle zero-length arrays. You could remove the asserts to fix that.

I’ve tested this with only the one array in the code (and only after deciding that my first draft would also be the final version ;-) ) but I think I have thought through all the edge cases…

public class SelectionSortTest
{
    public static void ssort(int[] a)
    {
        int last = a.length - 1;
        int smallestIndex;
        int tmp;

        for (int i = 0; i <= last - 1; i++)
        {
            smallestIndex = i;

            for (int j = i + 1; j <= last; j++)
            {
                if (a[j] < a[smallestIndex])
                {
                    smallestIndex = j;
                }
            }

            tmp = a[i];
            a[i] = a[smallestIndex];
            a[smallestIndex] = tmp;

        }
        
    }

    public static void printArray(int[] a)
    {
        for (int i = 0; i <= a.length - 1; i ++)
        {
            System.out.println(a[i]);
        }
        
    }

    public static void main(String[] args)
    {
        int[] a = {2, 1, 3, 1, 1};

        ssort(a);

        printArray(a);
    }
}

@Paul Winkler – yes, I think you’re right on both counts. Deleting the input is really not what a caller would expect!

It’s odd, but for these sorts of things I always go back to plain C.

void ssort(int nums[], int numNums)
{
	int i, j;
	
	for (i=0; i<numNums; i++)
	{
		for (j=i+1; j<numNums; j++)
		{
			if (nums[j] < nums[i])
			{
				int t = nums[i];
				nums[i] = nums[j];
				nums[j] = t;
			}
		}
	}
}

First time setting up invariants, bound function and pre/postconditions. I’m not sure I did it right but the function seem to do what it should…

/*
 * Invariant: if val at any position i in an array array of length len
 *  is lower	than the current value at j in the array the value is at 
 *  an i > j and i < len
 *
 * bound function: 0 <= j < length - 1
 *								 j <  i < length
 *
 * precondition:  a[] is an unsorted array of integers of the size len
 * postcondition: a[] is an array sorted higher to lower
 * */
void selectSort(int a[], int len)
{
	int tempStore, i, j;

	for (j = 0; j < len - 1; j++)
	{
		for (i = j + 1; i < len; i++)
		{
			if (a[i] < a[j])
			{
				tempStore = a[j];
				a[j] = a[i];
				a[i] = tempStore;
			}
		}
	}
	return;
}

Praying that the source-bracketed source shows up as source…

Got it nearly right the first time – input with MAXINT in it resulted in an endless loop.

public class SelectionSort
{
    public static List<Integer> sort(int[] data)
    {
        final LinkedList<Integer> result = new LinkedList<Integer>();

        int lowerBound = Integer.MIN_VALUE;
        boolean found;

        do
        {
            found = false;
            int currentMin = Integer.MAX_VALUE;
            int count = 0;
            for (int elem : data)
            {
                if (elem >= lowerBound) // >= because of Integer.MIN_VALUE
                {
                    if (elem < currentMin)
                    {
                        currentMin = elem;
                        count = 1;
                        found = true;
                    }
                    else if (elem == currentMin)
                    {
                        count++;
                        found = true; // special case - min element is Integer.MIN_VALUE
                    }
                }
            }
            for (int i = 0; i < count; i++)
            {
                result.add(currentMin);
            }
            if (currentMin == Integer.MAX_VALUE)
            {
                break;
            }
            lowerBound = currentMin + 1;
        }
        while (found);

        return result;
    }
}

perl, just because it’s quickest for me to code.

takes an array ref and sorts in-place.

seems to work in the tests I ran it through (after completing coding, naturally): an array with 100 random ints, an array with 100 of the same int, an array with 100 ints already in sorted order, an array with a single element and an empty array.

sub selection_sort {
    my $unsorted = shift;

    # iterate array
    for ( my $i = 0; $i <= $#$unsorted; $i++ ) {
	# scan to the right of $i
	for ( my $j = $i + 1; $j <= $#$unsorted; $j++ ) {
	    # is our candidate lesser than the value at $i?
	    if ( $unsorted->[$j] < $unsorted->[$i] ) {
		# stash new lesser value
		my $tmp = $unsorted->[$j];
		# swap old element to $j
		$unsorted->[$j] = $unsorted->[$i];
		# and put new element in at $i
		$unsorted->[$i] = $tmp;
	    }
	}
    }

    return 1;
}

Here’s a shot at in place:

def selection_sort(array)
  n = array.size
  c = 0
  while c < n
    i = 0
    imin = 0
    while i < (n - c)
      imin = i if array[i] <= array[imin]
      i += 1
    end
    array.push(array.delete_at(imin))
    c += 1
  end
  array
end

/** Sort an array in ascending order in-place.
 * 
 * The array contains n values. array may not be NULL, but n can be zero.
 * The array may contain duplicate values.
 */
void selection_sort(int* array, size_t n) {
    if (n > 0) {
        for (int* target = array; (target+1) != (array+n); ++target) {
            int* smallest = target;
            for (int* test = target+1; test != (array+n); ++test) {
                if (*test < *smallest)
                    smallest = test;
            }
            int tmp = *target;
            *target = *smallest;
            *smallest = tmp;
        }
    }
}

Compiled, and tested with n==0, n==1, descending, ascending, and duplicate values. Worked first time, though my “is_sorted()” function used for testing had a bug (>= vs >).

Seems to work with single, random, sorted and co. array.
Any way, may be buggy but it was always fun to quick write some c89 codes like that, back of the day. More!

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

int*
selection_sort (int* array, size_t n)
{
  if ((array == NULL))
    return NULL;

  size_t stash_bound = 0;
  while (stash_bound < n)
    {
      size_t smallest_value_pos = stash_bound;
      int    value_to_move_away;
      int    smallest_value;
      size_t i;

      /* find */
      for (i = stash_bound; i < n; ++i)
        {
          if (array[smallest_value_pos] > array[i])
            smallest_value_pos = i;
        }

      /* save */
      smallest_value     = array[smallest_value_pos];
      value_to_move_away = array[stash_bound];

      /* swap */
      array[smallest_value_pos] = value_to_move_away;
      array[stash_bound]        = smallest_value;

      /* push */
      ++stash_bound;
    }

  return array;
}

This time my first try worked! Inherently simpler algorithm than binary search, I guess, or maybe I was just more careful. Here’s my answer in PLT Scheme:

(define (selection-sort l)
  (if (null? l)
      null
      (let ((m (apply min l)))
	(cons m (selection-sort (remq m l))))))

If using “min” with more than two arguments is cheating, then replace “(apply min l)” with “(foldl min (car l) (cdr l))”.

Ah well, I just realized my solution only works with exact numbers, because of inexact contagion in min. Change remq to remv and it works for all numbers. (And that last line was indented with a tab, which for some reason WordPress converts to 4 spaces instead of 8.)

Fail. Turns out remv doesn’t work either for lists containing inexact numbers; you have to use “(remove m l =)”. Or just redefine min with “(define (min x y) (if (< x y) x y))" and remq works in the original solution. Sigh.

Here goes nothing…

def swap(lst, x, y):
    """Swap (in place) two items in a list given positions pos1 and pos2."""
    temp = lst[y]
    lst[y] = lst[x]
    lst[x] = temp

def selection_sort(lst):
    """Return a sorted list using selection sort."""
    lst = lst[:] # Don't modify the original list
    for cur_index in range(len(lst) - 1):
        # Find the smallest item in the remaining list
        min_index = cur_index
        for i in range(cur_index + 1, len(lst)):
            if lst[i] < lst[min_index]:
                min_index = i
        swap(lst, cur_index, min_index)
        cur_index += 1
    return lst

Doug Orleans: Sounds like Scheme isn’t the language for you, eh?

Doug Orleans, that’s a real shame. Your Scheme version of selection sort was my favourite of all the submissions so far, and a nice advertisement for how concise and elegant Lisp can be.

Language: JavaScript / ECMAScript

Damnit! Had 2 bugs, guess it was just late… I added code that reverses the end result by mistake and IN that code I had a bug that caused an endless loop.
Loving this series by the way! Had never written a selection sort or binary search before, languages or frameworks take care of that for me usually.

WAS:

/**
 * Sort an array with selection sort (slow) in JavaScript
 */
function selectionSort(unsorted)
{
    var sorted = [];
    var lastMin, lastMinPos, valuesLeft;

    do {
        lastMin        = undefined;
        lastMinPos = undefined;
        valuesLeft = false;

        for (var i = 0; i < unsorted.length; i++) {
            if (typeof unsorted[i] === 'undefined') {
                continue;
            }

            // defined value found
            valuesLeft = true;
            if (+lastMin < +unsorted[i]) {
                continue;
            }
            
            // New minimum found or NaN for curent minimum
            lastMinPos = i;
            lastMin = unsorted[i];
        }

        if (lastMin) {
            sorted[sorted.length] = lastMin;
            delete unsorted[lastMinPos];
        }
    }
    while (valuesLeft === true);
    
    // Reverse the array
    var sortedProper = [];
    for (var j = sorted.length - 1; j >= 0; j++) {
        sortedProper[sortedProper.length] = sorted[j];
    }

    return sortedProper;
}

SHOULD HAVE BEEN:

/**
 * Sort an array with selection sort (slow) in JavaScript
 */
function selectionSort(unsorted)
{
    var sorted = [];
    var lastMin, lastMinPos, valuesLeft;

    do {
        lastMin    = undefined;
        lastMinPos = undefined;
        valuesLeft = false;

        for (var i = 0; i < unsorted.length; i++) {
            if (typeof unsorted[i] === 'undefined') {
                continue;
            }

            // defined value found
            valuesLeft = true;
            
            console.log(lastMin, unsorted[i]);
            if (+lastMin < +unsorted[i]) {
                continue;
            }
            
            // New minimum found or NaN for curent minimum
            lastMinPos = i;
            lastMin = unsorted[i];
        }

        if (lastMin) {
            sorted[sorted.length] = lastMin;
            delete unsorted[lastMinPos];
        }
    }
    while (valuesLeft === true);

    return sorted;
}

In Java:

	private static void sort(int[] arr) {
       // Selection sort, probably not quite as efficient as possible, but I think it works
		for (int i = 0; i < arr.length; i++) {
			int min = i;
			for (int j = i; j < arr.length; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			// minimum index is j
			// swap arr[i] and arr[min]
			int tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}
	}

Here’s another C++/STL version. Succeeds on all the edge cases I could think of.

I passed by the skin of my teeth. My initial draft had a pretty serious bug, and just before I was about to hit Run, I noticed it and rewrote.

vector<int> selsort(const vector<int>& input)
{
   vector<int> working = input;
   
   for(unsigned int ii=0; ii<working.size(); ii++)
   {
      int winner = numeric_limits<int>::max();
      int winning_index = -1;

      for(unsigned int jj=ii; jj<working.size(); jj++)
      {
         if (working[jj] < winner)
         {
            winner = working[jj];
            winning_index = jj;
         }
      }
      swap(working[ii], working[winning_index]);
   }

   return working;
}

@Arild

Thanks for helping with the clarification. And yeah, it’s fun what sort of complexity you can avoid if you just ignore one of the performance constraints. (O(1) additional space in this case.)

@mdhills

It’s O(N^2) time just like all the others, but it’s definitely not O(1) additional space like a proper selection sort is. I think there are definitely a few conceptual hurdles to being able to read haskell (or ml, etc.) code — pattern matching, the way the particular language says “cons,” etc. — but once you get your head around it works out pretty well. (Although I still have trouble reading point-free code….)

Here it is in C. Seems to work, though admittedly not tested particularly exhaustively (couldn’t think of edge cases beyond the empty array and an array with multiple values the same).

void selsort(int *arr, int len) {
  int i;
  for (i=0;i<len;i++) {
    int j,minj,minval;
    minj = i;
    minval = arr[i];
    for (j=i;j<len;j++) {
      if (arr[j] < minval) {
        minj = j;
        minval = arr[j];
      }
    }
    arr[minj] = arr[i];
    arr[i] = minval;
  }
}

My in place python solution. This worked the first time and passed all the tests I could think of. I did spend a lot of time thinking it through (I failed the binary search test.)

def sort(li):
    for j in range(len(li)):
        index = j
        for i in range(j, len(li)):
            if li[i] < li[index]:
                index = i
        # switch elements
        li[j],li[index] = li[index],li[j]

I’ve put mine up at http://gist.github.com/408553 along with test cases derived from the next post.

Worked perfectly first time: I have redeemed myself!

I wrote that on my iPhone the other night… and quickly verified that it compiles (forgot a semicolon) this morning.

That said no testing, no reading, so the code is likely to be wrong…

That’s C/C++ code.

void sort(int* array, const int size) {
  // precondition
  assert(size>0 && array);

  // insert loop
  for (int low=0; low<size; ++low) {
    // search min loop
    int min_index = low;
    int min_value = array[low];
    for (int i=low+1; i<size; ++i) {
      if (array[i] <= min_value) {
        min_index = i;
        min_value = array[i];
      }
    }

    // swap min value (or noop if no min found)
    array[min_index] = array[low];
    array[low] = min_value;
  }
}

Sigh, once again, with code tags. Ruby, in place:

def selection_sort(array)
  start = 0
  while start < array.size
    low = start
    start.upto(array.size - 1) do |k|
      low = k if array[k] < array[low]
    end
    array[start], array[low] = array[low], array[start]
    start += 1
  end
  array
end

It sorted correctly the first time I ran it:

template <typename It>
void selection_sort(It begin, It end) {
  for (It cur = begin; cur != end; ++cur) {
    It min = cur;
    for (It it = cur + 1; it != end; ++it) {
      if (*it < *min) {
        min = it;
      }
    }
    std::iter_swap(min, cur);
  }
}

I noticed nobody used the old xor trick to swap the element values. Probably just as well :)

Haskell:

import Data.List
selection_sort xs = selsort xs []
  where { selsort [] acc = acc
        ; selsort xs acc =
             let { least = minimum xs }
              in selsort (delete least xs) (least:acc) }

Now that I’m committed to the above code, I’ll go test it and report back, as per the rules. (Time passes.)

I tested it and it works on the empty list but messes up precisely in that elements are sorted in reverse order. The correct code is

import Data.List
selection_sort xs = selsort xs []
  where { selsort [] acc = acc
        ; selsort xs acc =
             let { least = maximum xs }
              in selsort (delete least xs) (least:acc) }

‘maximum’ instead of ‘minimum’. Count me as another coder who can’t write correct code the first time around (even if the fix took < 10ms).

Failure.

php:

function ascSort($A) {
	$new = array();
	while(!empty($A)) {
		foreach($A as $i => $v) {
			(isset($lowest) && ($v > $A[$lowest])) or $lowest = $i;
		}

		$new[] = $A[$lowest];
		unset($A[$lowest]);
		unset($lowest);
	}
	return $new;
}

I noticed nobody tried the old trick-sort trick.

void tricksort(int array[], int numElements)
{
    memset(array, '\0', numElements*sizeof(int));
}

The result [i]is[/i] a sorted array ;)

def ssort(alist):
    n = len(alist)
    result = []
    for i in range(n):
        pmin = i
        for j in range(i+1, n):
            if alist[j] < alist[pmin]: pmin = j
        result.append(alist[pmin])
        if pmin != i:
            alist[pmin] = alist[i]
    return result

But I had one error: the first range was range(n-1) initially

:’-(

Eventually I’ll catch one of these on a day when I’m writing in ruby, but today we get JavaScript.

// Numerical in-place selection sort;
//
// * Assumes 'list' is an array instance.
// * Assumes 'list' contains only actualy numbers
//

var find_min_from = function(list, index) {
    var min_val = list[index];
    var min_index = index;
    for (; index < list.length; ++index) {
        if (list[index] < min_val) {
            min_val = list[index];
            min_index = index;
        }
    }
    return min_index;
};


var move_min_to = function(list, index) {
    var min_index = find_min_from(list, index);
    var tmp = list[index];
    list[index] = list[min_index];
    list[min_index] = tmp;    
};


var selection_sort = function(list) {
    for (var i = 0; i < list.length; ++i) {
        move_min_to(list, i);
    }
};

Shorter version:

Haskell> let sor = go [] where go ys [] = ys; go ys (x:xs) | all (x>=) xs = go (x:ys) xs | otherwise = go ys (xs++[x])
Haskell> :m + Test.QuickCheck
Haskell> quickCheck $ \xs -> sort xs == sor xs
OK, passed 100 tests.

Appears to be correct based on comparison of 1e8 randomly populated arrays. Wish I could have participated in the last one, but I didn’t see the “don’t test until finalized” instruction until it was too late :P

   public static void sort(int[] array) {
      
      if (array.length < 2) return;
      
      // For each element in the array
      for (int i=0; i<array.length-1; i++) {
         
         // find the index of the smallest element in the array at or above the current position and
         int indexOfSmallest = i;
         for (int j=i+1; j<array.length; j++) {
            if (array[j] < array[indexOfSmallest]) indexOfSmallest = j;
         }
         // swap it with the current element
         int temp = array[i];
         array[i] = array[indexOfSmallest];
         array[indexOfSmallest] = temp;
      }      
   }

C++. I think it works fully (at first), but I’ll have to read the follow-up article to know for sure ;)

void sort( int *v, int s )
{
    for( int cur = 0; cur < s; ++cur )
    {
        for( int i = cur + 1; i < s; ++i )
        {
            if( v[ i ] < v[ cur ] )
            {
                int t = v[ cur ];
                v[ cur ] = v[ i ];
                v[ i ] = t;
            }
        }
    }
}

My python function worked the first time it was executed:

def sort(_list):
  for lower in range(len(_list)):
    min_idx = lower
    min = _list[min_idx]
    for idx in range(lower, len(_list)):
      if _list[idx] < min:
        min_idx = idx
        min = _list[min_idx]
    _list[min_idx], _list[lower] = _list[lower], _list[min_idx]

I came late to the game but here is my untested entry, it should work fine. It’s C#

static void Sort (int[] array) {
    for (var i = 0; i < array.Length - 1; i++) {
        var minIndex = i;
        for (var j = i + 1; j < array.Length; j++) {
            if (array [j] < array [minIndex] ) 
                minIndex = j;
        }   
        array[i] ^= array [minIndex];
        array [minIndex] ^= array [i];
        array[i] ^= array [minIndex];
    }
}

Ok, just after posting i saw my stupid error caused by the swap, here is the corrected version:

static void Sort (int[] array) {
    for (var i = 0; i < array.Length - 1; i++) {
        var minIndex = i;
        for (var j = i + 1; j < array.Length; j++) {
            if (array [j] < array [minIndex] ) 
                minIndex = j;
        }   
        if (minIndex != i) {
            array[i] ^= array [minIndex];
            array [minIndex] ^= array [i];
            array[i] ^= array [minIndex];
        }
    }
}

I guess i should not rush in this kind of things.

Jeff Dege pointed out:

I noticed nobody tried the old trick-sort trick.

That’s because I explicitly addressed it it both the earlier precondition/postcondition article and the followup on how to test a sort routine.

Preconditions and postconditions are irrelevant to the issue of whether a trick sort meets the stated requirements.

A trick sort would clearly have failed the tests you described in your follow-on post.

But if you read the actual requirements you provided in this post, you don’t explicitly state that the resulting sorted output must contain the same elements as the unsorted input. You simply assume it. Which most folks do, when they express this problem.

Which is why it’s so common for the trick sort to be a correct solution for the problems of this sort – vague or incomplete requirements.

As for the complaints about the readability of Haskell, well, consider APL. The link is APL code for a quicksort, not a selection sort, but it clearly demonstrates that APL maintains its reputation for opacity:

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#APL

Late, but better than never? Tested on some obvious boundaries and a few “normal” arrays and it works for those. Point out where I’m wrong though. Looking forward to reading the follow up.

int selection_sort(int array[], int length) {
	int i;
	int current;
	int tmp;

	for(i=0; i < length; ++i) {
		current=find_min(array, i, length-1);
		tmp = array[i];
		array[i] = array[current];
		array[current] = tmp;
	}
}

int find_min(int array[], int low, int high) {
	int i;
	int min=low;

	for(i=low; i<=high; ++i) {
		if(array[i] < array[min]) {
			min=i;
		}
	}
	return min;
}

It’s C by the way… and I just noticed that the selection_sort function doesn’t properly return anything, and should probably be returning void anyway, so there’s that.

Finally, because I forgot to say it before because it seemed so obvious…

These posts are gold. If you did nothing but post this kind of stuff (including some future post on asymptomatic growth) I would keep reading.

I wrote mine in Common Lisp, with maximum recursion in mind, and I cons a lot :). It passed my tests first time:

(defun segregate (predicate list &optional (best nil bestp) accum)
  (if list
    (if bestp
      (if (funcall predicate (car list) best)
        (segregate predicate (cdr list) (car list) (cons best accum))
        (segregate predicate (cdr list) best (cons (car list) accum)))
      (segregate predicate (cdr list) (car list)))
    (values best accum)))

(defun selection-sort (list &optional (predicate #'<))
  (when list
    (multiple-value-bind (best rest) (segregate predicate list)
      (cons best (selection-sort rest)))))

Here’s an array version in Common Lisp that uses the iterate library:

(defun selsort (seq &optional (pred #'<))
  (let ((length (length seq)))
    (if (<= length 1)
      seq
      (iter (for i from 0 to (- length 2))
            (for mindex = i)
            (for minval = (aref seq mindex))
        (iter (for j from (1+ i) to (- length 1))
              (for jval = (aref seq j))
          (when (funcall pred jval minval)
            (setf mindex j minval jval)))
        (rotatef (aref seq i) (aref seq mindex))
        (finally (return seq))))))

I had one bug – using shiftf instead of rotatef, which made ‘swapping’ elements clobber one of the values, so I guess for this one, I kindof fail. For one thing, I feel a lot less comfortable writing functions with indices into arrays rather than recursion (the indices remind me of my study in numerical maths – shudder).

I did it! (at least according to my testing).

def sort(arr):
  # takes a list
  result = []

  while len(arr) > 0:
    smallest = 0
    for i in range(1, len(arr)):
      if arr[i] < arr[smallest]:
        smallest = i
    result.append(arr[smallest])
    del arr[smallest]
  return result

It doesn’t change the array in-place it creates a new one, and it modifies the input. So while it works I think that it’s not O(n^2) (because Python list entry deletion is O(n)).


	public class SelectionSort {
	private static int[] selectionSort(int[] values) {
	for(int firstUnsortedIndex = 0;
	firstUnsortedIndex < values.length;
	firstUnsortedIndex++) {
	swapValuesAt(values,
	firstUnsortedIndex,
	findIndexOfSmallestValueAfter(values, firstUnsortedIndex));
	}
	return values;
	}


	private static int findIndexOfSmallestValueAfter(int[] values, int startIndex) {
	int smallestValueSoFar = -1;
	int smallestValueIndex = -1;
	for (int candidateIndex = startIndex;
	candidateIndex < values.length;
	candidateIndex++) {
	int candidateValue = values[candidateIndex];
	if (isFirstValue(candidateIndex)
	\|\| candidateValue < smallestValueSoFar) {
	smallestValueSoFar = candidateValue;
	smallestValueIndex = candidateIndex;
	}
	}
	return smallestValueIndex;
	}


	private static boolean isFirstValue(int candidateIndex) {
	return candidateIndex == 0;
	}

	private static void swapValuesAt(int[] values,
	int firstIndex,
	int secondIndex) {
	int firstValue = values[firstIndex];
	int secondValue = values[secondIndex];

	values[firstIndex] = secondValue;
	values[secondIndex] = firstValue;
	}
	}

view raw

Submission for Selection Sort Contest

hosted with ❤ by GitHub

Language: Java
Time Taken: around 20 minutes.

Granted, it is not the shortest possible solution, but each method in there is pretty readable and clear, so this gives me a certain confidence that this might work.

(Just stuffed some values in it, and I got some -1 somewhere. Splendid.)

In Ruby:

def selection_sort!(ary)
	(ary.size-1).times do |i|
		min = i
		i.upto(ary.size-1) do |x|
			min = x if ary[x] < ary[min]
		end
		ary[i], ary[min] = ary[min], ary[i]
	end
	ary
end

! for the Ruby-idiom of showing in-place operations. I didn’t feel like making a new array.

For the non-Rubyists:

number.times do |i|
	Iterates from zero to (number-1), passing that value to i on each loop.
i.upto(number) do |x|
	Iterates from i to number, passing that value to x on each loop.
x = y if (boolean statement)
	Only performs left-side of if statement if the statement is true.
x,y = y,x
	Swaps entries (no need for a temp variable)
second-to-last-line: ary
	Ruby returns the last left-hand value.  Without this, it'd return "number", because that's what .times returns.

Requires an array, but size shouldn’t matter, nor contents, as long as they’re comparable (include Comparable module and define method).

Oops, is there a way to edit? No?

~2 minutes, tested after wrote, worked on all I passed it.

@Vince: that reminds me of this, the XOR’d doubly-linked-list with a single pointer: http://en.wikipedia.org/wiki/XOR_linked_list

I realize this is a few days late, but hey – it was fun to do.

Compiled and ran correctly the first time (including the test code).

Total time about 20 minutes. Language is Perl.

#!/usr/bin/perl

use strict;
use warnings;

my $success = 1;
foreach my $type_of_list qw(random empty flat only_one sorted reversed flat_at_start flat_at_end only_two_sorted only_two_reversed) {
my $items = list_of_values($type_of_list);
my $selection_sorted_items = selection_sort($items);
if (not correctly_sorted($selection_sorted_items, $items)) {
$success = 0;
print “Failure: $type_of_list list\n”;
}
}
if ($success) {
print “Success\n”;
}
exit;

##########################################
# Performs a selection sort on the passed list of values
sub selection_sort {
my $values = shift;

my $sorted_values = [];
my @remaining_values = @$values;
while (0 < @remaining_values) {
my $lowest_value = shift @remaining_values;
foreach my $entry (@remaining_values) {
if ($entry < $lowest_value) {
my $scratch_value = $lowest_value;
my $lowest_value = $entry;
$entry = $scratch_value;
}
}
push (@$sorted_values, $lowest_value);
}
return $sorted_values;
}

##########################################
# Returns 1 if the list is correctly sorted, 0 if not
sub correctly_sorted {
my ($items_list, $raw_list) = @_;
return 0 unless (@$items_list == @$raw_list);
my $last_value;
foreach my $entry (@$items_list) {
if ((defined $last_value) && ($entry < $last_value)) {
return 0;
}
$last_value = $entry;
}
return 1;
}

##########################################
# Returns a test list of integer values
sub list_of_values {
my $list_type = shift;

if ($list_type eq 'empty') {
return [];

} elsif ($list_type eq 'only_one') {
return [1];

} elsif ($list_type eq 'only_two_sorted') {
return [1,2];

} elsif ($list_type eq 'only_two_reversed') {
return [2,1];

} elsif ($list_type eq 'flat') {
return [2,2,2,2,2,2,2];

} elsif ($list_type eq 'flat_at_start') {
return [2,2,2,2,2,2,1];

} elsif ($list_type eq 'flat_at_end') {
return [1,2,2,2,2,2,2];

} elsif ($list_type eq 'random') {
return random_list(20,-32768,32767);

} elsif ($list_type eq 'sorted') {
my $sorted_list = [ sort {$a $b} random_list(20,-32768,32767) ];

} elsif ($list_type eq ‘reversed’) {
my $sorted_list = [ sort {$b $a} random_list(20,-32768,32767) ];

} else {
die(“Unimplemented test list type: $list_type\n”);
}
}

##########################################
# Returns a random list of integer values
sub random_list {
my ($n,$min_value,$max_value) = @_;

my $range = $max_value – $min_value + 1;

my $values_list = [];
for my $counter (1 .. $n) {
push(@$values_list, int(rand($range)) + $min_value);
}
return $values_list;
}

Oops. Looks like I failed. :( After extending my tests to check that the sorted lists do in fact have all the numbers in the original lists, it does not in all cases.

Now to figure out my mistake…

Ah. Line 33. I typoed a ‘my’ at the start of the line.

here’s mine. failed the first time because i started writing it one way (with the variable min holding on to the value of the smallest element, rather than the index of it), and i forgot to update the swapping code when i made that change. woops :P

i also accidentally tossed in a semi-colon on one line because i’ve been coding in java all week at work.

#!/usr/bin/env python

def selsort(a=[]):
	for i in range(len(a)):
		min = i # min=index of min value
		for h in range(i, len(a)):
			if a[h] < a[min]: min = h
		if (min != i):
			tmp = a[i]
			a[i] = a[min]
			a[min] = tmp
	return a

Failed the first time. Forgot “defined”.

#!/usr/bin/env perl

use strict;
use warnings;

my %in;
$in{$_}++ foreach @ARGV;
my @out;

while (%in) {
    my $min;
    foreach my $in (keys %in) {
        $min = $in if (! defined $min or $in < $min);
    }
    unshift @out, $min;
    delete $in{$min} unless --$in{$min};
}

print join (', ', @out) . "\n";

I believe I succeeded! It worked against all the test cases assuming that I tested them correctly. I’m fairly happy since this is my first Ruby program that actually does something. Although, I’m sure it could be better.
In addition I really do feel that selection sort is easier than binary search but that could be because the binary search already got me thinking more.

def selectionSort(toSort)
  if !toSort.nil? && toSort.size > 0
    #Find smallest
    toSort.each_index do |index|
      if toSort[index] < toSort[0];
        swap = toSort[0];
        toSort[0] = toSort[index];
        toSort[index] = swap;
      end
    end
    #Sort the remainder and concat
    toSort.slice(0..0) + selectionSort(toSort.slice(1..(toSort.size-1)))    
  else
    toSort
  end
end

#!/usr/bin/python

def sort_array(array):
   # smallest element is always at the end of the array
   # largest element is always at the start of the array
   # loop terminates when the number of items sorted is equal to the number of items in the array
   # next smallest element always ends up just previous to the last smallest element 
   for elements_to_sort in range(len(array), 0, -1):
      current_smallest_index = 0
      for index in range(0, elements_to_sort):
	      if array[index] < array[current_smallest_index]:
	         current_smallest_index = index
      swap(array, current_smallest_index, elements_to_sort-1)
   return array

def swap(array, index1, index2):
   value1 = array[index1]
   array[index1] = array[index2]
   array[index2] = value1

Around 40mins in python because the tv is on :)

Using python.

The first time I was printing the results stupidly, but the actual sort function worked just fine.

#!/usr/bin/python

def selection_sort(to_sort):
	sorted	= []
	
	while(len(to_sort) > 0):
		smallest = None
		for elem in to_sort:
			if smallest == None or elem < smallest:
				smallest = elem
		
		sorted.append(smallest)
		to_sort.remove(smallest)
		
	return sorted
	
sorted = selection_sort([0,10,2938,21,5,9,8,7,8,67,6,37,6,38,73])

for i in sorted:
	print i

prints the expected:

0
5
6
6
7
8
8
9
10
21
37
38
67
73
2938

I fail due to choosing an unfamiliar language/style combination: I tried to do it statefully in Haskell. I wrote my sort on paper during a boring meeting, so I couldn’t look up Haskell’s Array (of which I couldn’t remember the names of basic operations) and ST (which I had confused with something much simpler), so I didn’t finish converting pseudocode into valid Haskell. Had I done so, it would still have failed its tests, because in the selection step, I was obliviously searching the original array instead of the modified array.

Incidentally, because this was Haskell, I felt compelled to write the selection as a pair of folds with enumFromTo instead of explicit recursion. The folds were shorter but seemed to me harder to verify, because their base cases were less explicit.

Took me about 30 minutes to write and mentally verify the solution (Visual Studio 2010 with R# 4.5). Language of choice was C# 3.

Algorithm – http://gist.github.com/414931

Full program – http://gist.github.com/414942

The initial implementation passed all my tests so I would say I succeeded :-).

PHP version, tested with empty, single element and multi elment arrays, including duplicated entries. Output was checked against the one produced by the library function sort. Seems to work fine. Time was around 15 minutes.

/* 
 * precondition:   src is a one-dimensional array of any size, whose values can be compared
 *                 using the standard operators <, >, ==
 * postcondition:  src is a copy of the input array, sorted in ascending order
 */
function selectionSort($src)
{
  /* invariant: src[m] <= src[n], for 0 <= m <= n < i < size
   * bound function: size-i */
  for($i = 0, $size = sizeof($src); $i < $size; ++$i)
  {
    /* invariant: src[i] <= src[k], for 0 <= i < k < size
     * bound function: size-k */
    for($k = $i+1; $k < $size; ++$k)
    {
      if($src[$k] < $src[$i])
      {
        $tmp = $src[$i];
        $src[$i] = $src[$k];
        $src[$k] = $tmp;
      }
    }
  }
  return $src;
}

Sorry rphan your first try is wrong, what if all the integers are negative? You should always pick a pivot in the array/

My implementation in Clojure:

(defn ssort [col]
 (if (empty? col) col
  (let [m (apply min col)]
   (cons m (ssort (filter #(not= m %) col))))))

I realized after running a couple quick tests that the filter will remove duplicate entries. So I guess I fail :(

(ssort [4 3 4 2 2 1 3]) would return (1 2 3 4)

In-place sort in C++. Right first time if my test cases are to be believed (and if I understood the algorithm description). Tested: (1) empty array, (2) one element, (3) already-sorted array, (4) array with duplicates. Hope my code formats correctly…

template <typename It>
void inplaceSelectionSort(It const b, It const e)
{     
  for (It i = b; i != e; ++i)
  {
    It smallest = i; 
    It j = i;
    for (++j; j != e; ++j)
      if (*j < *smallest)
        smallest = j;
    if (smallest != i)
      swap(*i, *smallest);
    // Post-condition: for all k: *i <= *k if i < k < e
  }
  // Post-condition: for all b,k: *i <= *k if b <= i < k < e
}

I haven’t tested it very carefully, but it seems to work.

void sort(int a[], int len)
{
	int lower, upper, min, i, imin;
	
	lower = 0;
	upper = len - 1;
	for (lower = 0; lower < upper; ++lower) {
		min = a[lower];
		imin = lower;
		for (i = lower+1; i < upper; ++i) {
			if ( a[i] < min ) {
				min = a[i];
				imin = i;
			}
		}
		swap(a, lower, imin);
	}
}

Java implementation. First try.. failed.
Total failure.Great insuccess! :-D

I have forgotten a “=” (I have put a < in place of <= ) what a shame!

My final Java code is:

 public static void selectionSort(ArrayList<Integer> array){
        if (array==null||array.isEmpty()) {
            return;
        }
        int startPosition = 0;
        int endPosition = array.size()-1;

        while(startPosition<endPosition){
            for(int currentPosition=startPosition; currentPosition<=endPosition; currentPosition++) {
                if(array.get(startPosition)>array.get(currentPosition)) {
                    Collections.swap(array, startPosition, currentPosition);
                }
            }
            startPosition++;
        }

    }

my complete test-suite is:

package selectionsort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 *
 * @author Fabiano :-(
 */
public class Main {

    
    public static void main(String[] args) {
        //ArrayList<Integer> arrayProva = new ArrayList<Integer>(Arrays.asList(10, 3, 5, 77, 9));
        //ArrayList<Integer> arrayProva = null;
        //ArrayList<Integer> arrayProva = new ArrayList<Integer>(Arrays.asList(10));
        ArrayList<Integer> arrayProva = new ArrayList<Integer>(Arrays.asList(10,2));
        selectionSortTest(arrayProva);
    }

    public static void selectionSort(ArrayList<Integer> array){
        if (array==null||array.isEmpty()) {
            return;
        }
        int startPosition = 0;
        int endPosition = array.size()-1;

        while(startPosition<endPosition){
            for(int currentPosition=startPosition; currentPosition<=endPosition; currentPosition++) {
                if(array.get(startPosition)>array.get(currentPosition)) {
                    Collections.swap(array, startPosition, currentPosition);
                }
            }
            startPosition++;
        }

    }

    public static Boolean isRightOrder(ArrayList<Integer> array){
        if (array==null||array.isEmpty()) {
            return true;
        }
        
        Integer previousObject =  array.get(0);
        for(Integer currentObject:array) {
            if(currentObject<previousObject){
                return false;
            }
        }
        return true;
    }

    public static void selectionSortTest(ArrayList<Integer> arrayTest){
        if (arrayTest!=null) {
        System.out.println("Original array"+arrayTest.toString());
        }

        selectionSort(arrayTest);

        if (arrayTest!=null) {
        System.out.println("Sorted array"+arrayTest.toString());
        }
        
        if(isRightOrder(arrayTest)) {
            System.out.println("Sorting has worked fine");
            return;
        } else {
            System.out.println("Sorting has NOT worked fine");
        }
    }

}

There are no excuse, I have failed
What a shame.

P.s: I have posted the “working” code

P.s2: I have implemented an in-place selection sort.

@Pontus
it looks like your solution/code is wrong it doesn’t manage the last array’s element! (IMHO)

Sorry for my being late but I’ve just seen the article and I hope to be still in time for posting.
It took me about 30/40 minutes to write and test on paper. C code. Worked on first try. No bugs.

void SelectionSort (int *v, int dim)
{
  int i, j, min, pivot, swap, temp;

  for (i = 0; i<dim-1; i++) {
    min = v[i];
    swap = 0;

    for (j = i+1; j<dim; j++) {
      if (min > v[j]) {
        min = v[j];
        pivot = j;
        swap = 1;
      }
    }

    if (swap) {
      temp = v[i];
      v[i] = v[pivot];
      v[pivot] = temp;
    }
  }
}

I loved Doug Orleans’s Scheme solution (since I grepped for all Scheme solutions before submitting mine, just to see if anyone used my approach), though, it’s one I’d never have written: I’m too big on tail calls, and converting Doug’s solution to tail calls would probably have doubled its length.

Here’s my solution, which is vector-based rather than list-based. It works with empty vectors, singleton vectors, as well as “3 1 4 1 5 9 2 6 5 3 5”. :-P

(require srfi/1 srfi/43)
(define (selection-sort! vec (lt <))
  (let ((size (vector-length vec)))
    (define (loop-iter i)
      (define (range-min)
        (define (min-iter l r)
          (if (lt (vector-ref vec r) (vector-ref vec l)) r l))
        (reduce min-iter #f (iota (- size i) i)))
      (vector-swap! vec i (range-min)))
    (for-each loop-iter (iota size)))
  vec)

Like my solution for binary search, you can pass in a custom predicate, so by using > you can sort by descending order, for example. (Then, after such sorting, use the same predicate for doing the binary search.)

None of the SRFI 1 nor SRFI 43 functions I used are particularly magical (not anything like finding the minimum element of a vector :-P); they just allow me to use things like reduce, iota, and vector-swap! without having to write them myself. :-P

P.S. It goes without saying that (just like my binary search submission) I have not changed the program since testing it, and it does work first time. :-P

The program works with PLT/Racket. You will need to adjust the SRFI loading lines if you’re using a different implementation, as well as the syntax for optional parameters (if your implementation supports it).

Refactored version that doesn’t look quite so scary (what with 4 levels of nested functions in the original). :-P

(require srfi/1 srfi/43)
(define (selection-sort! vec (lt <))
  (define size (vector-length vec))
  (define (min-iter l r)
    (if (lt (vector-ref vec r) (vector-ref vec l)) r l))
  (define (loop-iter i)
    (define (range-min)
      (reduce min-iter #f (iota (- size i) i)))
    (vector-swap! vec i (range-min)))
  (for-each loop-iter (iota size))
  vec)

I must confess, I left out returning the array from the subroutine. So I DID sort the array on the first try …. the local array. I didn’t return it and so I printed the original unsorted array in the end.

So I claim a solid algorithm … just a fault interface :)

#!/usr/bin/perl
use Data::Dumper;
use strict;

my @a = ( 29271, 20764, 14617, 16804, 4591, 156, 6158, 30994, 4814, 5522 );
print Dumper \@a;

sub sel_sort {

   my @a = @_;
   my $u = 0+@a-1;

   foreach my $i (0 ... $u)
   {
      my $minn = $i;
      my $min = $a[$i];

      foreach my $j ($i+1 ... $u)
      {
         if ($a[$j] < $min)
         {
            $minn = $j;
            $min = $a[$j];
         }
      }

      if ($minn != $i)
      {
         my $x       = $a[$i];
         $a[$i]      = $min;
         $a[$minn]   = $x;
      }

   }

   return(@a);

}

my @b = sel_sort(@a);
print Dumper \@b;

Man! There were several bugs in my first trial. One of which was just a name error, but another one was more of the logical kind. I think you should have chosen between in-place sorting and creating a new sequence, since the former is obviously more tricky — reason why I chose it, very arrogantly ;-). Below python code, refactored and tested (seems to work for empty seq, singleton, all elements equal, reverse order, random elements including duplicates):

def SelectionSort(seq):
	''' Sort a sequence using selection sort algorithm, in-place. '''
	def minimal(seq, startIndex):
		''' tuple of minimal element of seq and its index '''
		minElement = seq[startIndex] ; minIndex = startIndex
		for index in range(startIndex+1,len(seq)):
			element = seq[index]
			if element < minElement:
				minElement = element ; minIndex = index
		return (minElement,minIndex)
	for index in range(len(seq)-1):
		(minElement,minIndex) = minimal(seq, index)
		del seq[minIndex]
		seq.insert(index, minElement)

I’m rather interested in your tests (also did the binary search one, and had this one correct at once). But I guess what they measure is a bit weird: not the ability to produce correct code, but the ability to produce correct code at once, without any test; which is not in my sense a sensible measure of programmer capacity. Hope I’m clear.
More precisely, these tests are biased. What I mean is there are various kinds of programmers, and there are good ones of every kind (see also your own post “the hacker, the architect and the superhero”). A common distinction is between “engineering” and “exploring” programmers. The latter start coding as soon as they have a clear enough “model” (mental image) to produce something hopefully useful, then *monitor* what the code actually does via feedback output, and update their model in accordance. The former first refine their model until they are rather sure it’s accurate, both in general outline and details, then only start coding with the presumption it should be correct. An interesting point is that for engineers a bug is just this, say a failure, while for explorators a bug is a useful source of information, if not of discovery.
I enjoy the exploratory coding style; not because it’s trendy (recent programming methodologies all support it), simply it fits my way. Above all, I find it more efficient in the long run, since it lends to learning new things. But your tests indeed favor the engineer style, don’t they?

Excellent point about different between engineers and explorers, spir; but don’t you think that even we natural explorers would be better programmers if we exercised our engineering muscles a bit as well? Like the way a natural musician can still improve his technique by practising scales. On this subject, see my earlier post Testing is not a substitute for thinking (binary search part 3).

“…don’t you think that even we natural explorers would be better programmers if we exercised our engineering muscles”

Yes, indeed, I fully agree. Especially since, in any discipline, it’s often easier and faster to improve our weaknesses than to improve our strengths, or even to mainain them. (again, hope I’m clear)
Thanks for giving me another motivation for putting in practice, and not only studying, methods like those introduced in later posts of yours (invariants, pre/post-conditions, etc) :-) I’m often confused in designing or implementating the kind of apps requiring a level of abstraction (that seems to fly) over my capacity; such tools may help, not only in having things right, but most importantly in better understanding key points.

Sorts list in-place. Seems to work on every test case I tried. Took 15 min to write & worked right the first time (I love Python); but I really had to reason about the end points of both loops. I also enjoyed your post on the invariants, pre/post-conditions.

def selection_sort(lst):
    for ptr in range(len(lst))[::-1]:
        for cntr in range(ptr): 
            if lst[cntr] > lst[ptr]:
                lst[cntr], lst[ptr] = lst[ptr], lst[cntr]

Perl. Took about 15 minutes, and seemed to work the first time out, at least on everything I’ve thought to test it on (in order, reversed, random, empty).

sub selection_sort {
    my @in = @_;
    my $n = $#in;

    for $i (0 .. $n){
        my $least = $in[$i];
        my $least_index = $i;
        for $j ($i+1 .. $n){
            if ($in[$j] < $least){
                $least = $in[$j];
                $least_index = $j;
            }
        }
        ($in[$i], $in[$least_index]) = ($least, $in[$i]);
    }
    return @in;
}

It took me about an hour to think through this carefully. I decided to use PHP (which I’m still learning) and try to do it as much as possible in terms of functional programming. It seemed to work when I tested it. :-) https://gist.github.com/898739

Untested.

sub selectionsort {
  my ($array) = @_;
  # invariant: array is a permutation of the original array such that
  #   array[0..i-1] contains the i smallest elements of array in
  #   ascending order.
  for (my $i = 0; $i < @$array; $i++) {
    my $m = $i;
    # invariant: array[m] is a smallest element of array[i..j-1]
    for (my $j = $i+1; $j < @$array; $j++) {
      if ($array->[$j] < $array->[$m]) {
        $m = $j;
      }
    }
    ($array->[$i], $array->[$m]) = ($array->[$m], $array->[$i]);
  }
}

Tested – looks like it works.

Here’s my attempt in Haskell. I passed, but initially I did miss out the recursive call to selection…I caught it before I ran the code, but only because I was going over it again. Normally I would have just run it.

selection :: [Int] -> [Int]
selection [] = []
selection (x:xs) = min : selection rest
	where
		(min,rest) = removeMin x xs [] 
		
removeMin :: Int -> [Int] -> [Int] -> (Int,[Int])
removeMin  x []  k = (x,k)
removeMin  x (y:ys) k
			| x < y     = removeMin x ys (y:k)
			| otherwise = removeMin y ys (x:k)

Also, after looking over the other Haskell solutions this one looks like the first one not to use library functions. It’s definitely simpler if you use them…

Written in AutoIt 3 (because it’s neat)

Func Swap( ByRef $ary, $e1, $e2 )
    Local $tmp
    $tmp = $ary[$e1]
    $ary[$e1] = $ary[$e2]
    $ary[$e2] = $tmp
EndFunc

Func SelectionSortTheBogosity( ByRef $ary )
    ; search and search until the LEAST element is found... ho hum
    ; and we'll be changing the array as we go because we can and it's easy
    Local $candidate, $i, $unsorted_array_start, $found_smallest_value

    If Not( IsArray( $ary ) ) Then
        Return
    EndIf

    $unsorted_array_start = 0
    While $unsorted_array_start <= UBound( $ary ) - 1
        For $candidate = $unsorted_array_start To UBound( $ary ) - 1
            $found_smallest_value = True
            For $i = $unsorted_array_start to UBound( $ary ) - 1
                If $ary[$candidate] > $ary[$i] Then
                    $found_smallest_value = False
                    ExitLoop
                EndIf
            Next
            If $found_smallest_value Then
                Swap( $ary, $unsorted_array_start, $candidate )
                $unsorted_array_start += 1
            EndIf
        Next
    WEnd
EndFunc

The code seems to work correctly since the first try. It definitely took me longer though–20 – 30 min. Then I had to sleep so I had the opportunity to look over it again the next day. Didn’t make changes though.

I also write a PrintElements function to print out the array contents before I wrote the Selection sort itself. That one I *did* test (and did have to debug a little). (AutoIt has library code for this but it outputs to MsgBox and I wanted the output to go to the console window instead.)

I’m concerned that my code has three loops ( While, For, For ) whereas the other entrants seem to get by with just two. Oh well.

About Binary Search: I wasn’t there for that contest, but I ran into the situation described all on my own: many months back, for whatever reason, I wanted to implemented that cool binary search I’d learned in college and much to my dismay I found that, yeah, it ain’t nearly as easy as it seemed back in class. So I’m confident that if I *had* entered it, my coding would have taken a *long*, long time.

—
Furry cows moo and decompress.

This time I managed to hold off from reading the comments before giving my own attempt a shot (I sadly ended up “cheating” on the binary sort test).
A simplistic implementation in Python – written, then ran once on a few test cases which all turned out all right. Realized that I don’t check that I’m actually comparing numbers just after testing though, so I reckon it’s a bit flawed.

def selectionSort(A):
    if(type(A) != list or len(A) == 0):
        return False
    i = 0 
    while(i < len(A) - 1): 
        smallest = i 
        j = i 
        while(j < len(A)):
            if(A[j] < A[smallest]):
                smallest = j 
            j = j + 1 
        A[i], A[smallest] = A[smallest], A[i]
        i = i + 1 
    return True

Your series of posts about the 10% programmers was a real eye-opener. Many thanks!

Python, failed first time. Took about 10 mins.

def PopMin(xs, last_min=None):
    """Remove the smallest item off xs and return it. If last_min is
    set, treat it as a hint that nothing smaller than this will appear
    in the sequence and return anything equal to it without searching
    further.

    Only works for sequences not containing None.
    """
    min = None
    for i, x in enumerate(xs):
        if x == last_min:
            min = x
            min_item = i
            break
        if min is None or x < min:
            min = x
            min_item = i
    # Remove xs[min_item] from the list
    # This line failed because I tried to re-set xs rather than
    # changing it.
    xs[min_item:min_item+1] = []
    return min

def SelectionSort(xs, ret=[]):
    last_min = None
    while xs:
        last_min = PopMin(xs, last_min)
        ret.append(last_min)
    return ret

Purely-functional version of selection sort in Scala with iterative behavior and using persistent collections. https://gist.github.com/1362070

fumbled…..
my very first test with an empty array gave rise to an outright ArrayIndexOutOfBoundsException!!!
(coding in Java)

private static int[] selsort(int[] a) {
		int lastIndex = a.length - 1;
		int current;
		int min = a[0];		// <--------------------
		int minIndex = 0;	// this is wrong, too!
		
		while (lastIndex > 0) {
			// min = a[0];
			// minIndex = 0;		// this is how it SHOULD be!
			for (int i = 0; i <= lastIndex; i++) {
				current = a[i];
				if (current < min) {
					min = current;
					minIndex = i;
				}
			}
			current = min;
			a[minIndex] = a[lastIndex];
			a[lastIndex] = current;
			lastIndex--;
		}		
		return a;
	}

This mistake is gross, indeed…. I can’t but feel a little ashamed.
Nice blog, Mike!

Thanks, Marco, and kudos for coming out with an honest account of your attempt! Your comment is #200 on this article, which is pretty good going.

Yep, more than a year and a half old and still steamin’ ;-)
You know, I’m reading the blog’s archives like some sort of serial novel (got in a couple of days ago, looking for a nice explanation of the differences between ‘functional’ and ‘imperative’…) and I must say that what I like more is the lack of all the fruitless criticisms I found in my peregrinations round the net (both on your side and on the commenters’ (more or less :-))
And I can’t wait to see if in the end you manage to tame the Schemer of A Thousand Parantheses… ssssst don’t spoil the surprise :-D ahah.
Oh dear, better get to bed I suppose………………………

Yes, it’s been delightful in running this blog to have got such constructive, insightful comments so very much of the time. (There are a few exceptions, really, but they are literally one or two percent of all comments.)

I’m delighted that you’re enjoying going through the old material. I’ve been toying desultorily with the idea of compiling a bunch of TRP articles into a book, since mostly they are (by design) not “timely” but deal with pretty universal themes. With that in mind, it’s encouraging to know that the old material is still interesting to people.

As guessed from names, selection-sort! is destructive, and selection-sort returns the sorted string.
I did as for the binary search, the algorithms are tested, but not modified after testing. You may find bugs though, because I only tested that the code was not lame, not for edge cases.
P.S. code is tail-optimized. Correct me if anyone sees they are not and please tell me why.
P.P.S. “(lt” means “(less-than-sign”, where less-than-sign is the less than sign (OMG it’s ascii 0x3C damn you wordpress).

(defun minInList(l)
(labels ((keep-score (lRest last-ind)
(if (null (cdr lRest))
(if (lt (car lRest) (nth last-ind l))
(- (list-length l) 1)
last-ind)
(keep-score (cdr lRest)
(if (lt (car lRest) (nth last-ind l))
(- (list-length l) (list-length lRest))
last-ind)))))
(keep-score l 0)))

(defun selection-sort (lInit)
(let ((lResult lInit))
((lambda () (labels ((min-as-car (lRest)
(if (null (cdr lRest))
lResult
(progn
(rotatef (car lRest) (nth (minInList lRest) lRest))
(min-as-car (cdr lRest))))))
(min-as-car lResult))))))

(defun selection-sort! (lInit)
(labels ((min-as-car (lRest)
(if (null (cdr lRest))
T
(progn
(rotatef (car lRest) (nth (minInList lRest) lRest))
(min-as-car (cdr lRest))))))
(min-as-car lInit)))

I failed miserably. Even after I have thought about the invariant of the algorithm, I still couldn’t get it right the first time.
package random;

public class SelectionSort {
public static void main(String[] args){
int[] a = {3,7,1,2,5,0,9};
sort(a);
for (int e:a){
System.out.print(e);
}
}
public static void sort(int[] arr){
int i =0;
while (i < arr.length-1){
int min = i+1;
for (int j = i+1; j arr[j]){
arr[min] = arr[j];
}
}
swap(arr, min,i+1);
i++;
}
}
public static void swap(int[] arr, int p1,int p2){
int tmp = arr[p2];
arr[p2] = arr[p1];
arr[p1] = tmp;
}
}

A function written in Python:

def selection_sort(digits):
    # base case
    if not digits:
        return ''

    # counters
    min_n, min_pos = digits[0], 0

    # loop through array, swap if smaller found
    for i, n in enumerate(digits):
        if digits[i] < min_n:
            min_n, min_pos = digits[i], i
    digits[0], digits[min_pos] = digits[min_pos], digits[0]

    # recursive call
    return str(digits[0]) + selection_sort(digits[1:])

I didn’t participate in the challenge, but I actually had cause to write a selection sort recently in real code. If you want to sort nodes on a graph, such that the next node in the array has some property relative to the ones before it (has the most connections to the previous elements in the array, in my case), the only sort function that will work that I can think of is selection sort.

I think I implemented it correctly. Let’s see what happens on testing.
http://ideone.com/1MZBlp

	Mike Taylor on British folk music update
	NickS on British folk music update
	femtohacker on British folk music update
	Mike Taylor on The Timeless Children is 90%…
	Scurra on The Timeless Children is 90%…

Another challenge: can you write a correct selection sort?

What is selection sort?

The rules

How to submit your code

209 responses to “Another challenge: can you write a correct selection sort?”

Leave a comment

RSS Feeds

Recent Posts

Recent Comments

Archives

Doctor Who, Series 5

Greatest Hits

Most viewed today/yesterday

Blog Stats

Another challenge: can you write a correct selection sort?

What is selection sort?

The rules

How to submit your code

Share this:

Related

209 responses to “Another challenge: can you write a correct selection sort?”

Leave a comment

RSS Feeds

Recent Posts

Recent Comments

Archives

Doctor Who, Series 5

Greatest Hits

Most viewed today/yesterday

Blog Stats