Insertion sort (Smalltalk)

From LiteratePrograms

Other implementations: ACL2 | C | C, simple | Eiffel | Erlang | Forth | Haskell | Io | Java | Lisp | OCaml | Python | Python, arrays | Ruby | Scala, list | Smalltalk | Standard ML | Visual Basic .NET

We describe an insertion sort implementation using Smalltalk. This example is only for illustration. Normally, you would use the sorting capabilities supplied by the standard object framework; for example, Squeak Smalltalk supplies a sortBy: message on the SequenceableCollection class, and a mergeSortFrom: to: by: method on ArrayedCollection for sorting a sublist.

Insertion sort

First we have to find an object on which to declare this sorting routine. One strategy is to use the class Array and extend it. The following code was written using Squeak Smalltalk.

<<insertion sort>>=
insertionSort: sortFun 
	"Sort self according to 'sortFun'"
	| el j |
	self
		doWithIndex: [:elem :index | 
			el := self at: index.
			j := index - 1.
			[j >= 1
				and: [(sortFun
						value: (self at: j)
						value: el) not]]
				whileTrue: [self
						at: j + 1
						put: (self at: j).
					j := j - 1].
			self at: j + 1 put: el]

This code is a literal translation from the Lisp version. Smalltalk has a feature called blocks that allows us to treat a piece of code as an object by putting square brackets around it. Using this, we can make this implementation generic so that it can be used with strings, numbers, objects and so on just by providing an appropriate sortFun comparator block.

So as you see the here implemented method takes as a parameter the sortFun function. The text within quotes is a comment, the | el j | introduces two local variables. The keyword self has a special meaning: it represents the currently active object (the same as this in C++). So the object sends a message to itself named doWithIndex, this takes a block with two parameters. Blocks are enclosed in [], the parameters and the program text is separate by | the block parameters are prefixed with a :.

The assignment is done either with ← or :=. In the Squeak Smalltalk interface, the ← symbol is rendered by typing '_'. As you can see the assignment works as follows. I send the at: message to self this is comparable to s[at] in C. The next assignment is easy to understand it just sets j.

The most interesting part follows:

[j >= 1 and: [(sortFun
		value: (self at: j)
				value: el) not]]
  whileTrue: [self

As you can see the text precedes the loop. This is fully congruent with the object message way of calling things. The given block evaluates to a Boolean object, and this understands whileTrue:. So the loops are not special as in other language, they are just messages sent to Boolean objects. The only piece of code that may be puzzling is the (sortFun part. Again, there is nothing special about blocks. They are simple objects, and you send them as many value: messages as the block takes arguments. so you can read it as

Call sortFun with the variable at index j in self and the saved object

Now the not is needed because we have to move the elements as long as the order is not ok.

We can try out the sorting method using this sample class method:

<<sample code>>=
insertionSortTest
	a := Array new: 5.
	a at: 1 put: 2.
	a at: 2 put: 7.
	a at: 3 put: 0.
	a at: 4 put: 5.
	a at: 5 put: 3.
	a insertionSort: [ :x :y | x < y ].
	^ a printString

Files in Squeak Smalltalk

To allow this method to be easily imported into Squeak Smalltalk, we place it in an .st file with the appropriate surrounding markup for importing into the Array class using file-in. The first is an instance method and the second a class method.

<<insertionSort.st>>=
!Array methodsFor: 'sorting' stamp:''!
insertion sort! !
!Array class methodsFor: 'testing' stamp:''!
sample code! !

To execute the class method, we merely type "Array insertionSortTest" in a workspace and select the "print it" option.

Download code