Imperative Style Selection Sort in OCaml

Exercise 2.2-2 of the book Introduction to Algorithms introduced the selection sort algorithm.  I decided to write it in OCaml in imperative style.

The selection sort algorithm sorts a list first by switching places of the smallest element of a given list with the first element of the list.  Then, it selects the smallest element of the rest of the list, and switch its place with the second element of the list.  The process is repeated until all elements are sorted.

Things I learnt

The first thing I learned in this exercise is to never start with ‘similar’ code and never copy and paste code!  I start writing the selection sort algorithm by saving over my insertion sort code because I thought it’ll just be a small tweak over that algorithm, but it was a bad idea!  I spent more time debugging it than I expected because I unnecessarily used the while loop from before inappropriately!  Starting from scratch would have given me less confusion and a more clear and fresh direction.

The second thing I learned is the use of while loop and for loop.  I already knew them, but this exercise more clearly demonstrates that when I want the expressions in a loop to execute until a certain condition, I use while loop, but if I want the expression to be done a certain number of times, then I should use a for loop.

For example, it makes sense to use the while loop in insertion sort, because in insertion sort, an element is inserted in the sorted list, and once it is inserted, there is no longer need to execute the while loop more, because the purpose of the while loop is to find where to insert the element.  But for the case of selection sort, to find the minimum element of a list, a comparison of the current minimum has to be made to all elements of the unsorted list.  That’s why a for loop is in place of the while loop of the insertion sort code.  Of course, a while loop with only the counter and no additional condition is just a for loop!  From now on I will consciously choose between them using this principle, until I learn otherwise.

The third thing I learned is the use of a temporary holder.  Because the algorithm involves switching elements, I need to construct a ref to hold an array element that is to be overwritten.  First, put the content of the element in the ref, then overwrite the element with the new element/information.  E.g. in my imperative selection sort

tmp := a.(!themin) ;
a.(!themin) <- a.(j) ;
a.(j) <- !tmp ;

tmp is a ref that acts as a place holder.  It holds the content of a.(!themin).  Then, a.(!themin) holds the content of a.(j), and a.(j) is then updated with the content of a.(!themin).

Still, writing selection sort in imperative style is pretty easy, and is much easier than writing it in functional style!