Bubble sort (Io)
From LiteratePrograms
BubbleSort is well famous, at least as an example "how not to do programming". But it's simply and that counts obviously. Here now a complete BubbleSort for Io (modeled after the Common Lisp solution.
I added the whole stuff to the Protoyp List again (but be aware a List in Io is an resizable array) so this solution is not that worth as if we'd have a linked List...
List do (
bubbleSort := method(cmpBlock,
for(i, size -1 , 0, -1,
for(j, 0, i, 1,
if ((cmpBlock call(at(i),at(j)))
,
swapIndices(j,i)
))))
)
I used a block again as in the Insertion Sort, but will implement other approaches of using function (or blocks) later I think you'd hardly finda a more concise algorithm in any of the languages. Let's talk about a few area
bubbleSort := method
This creates a new method named bubbleSort and because before we have an List do we are extending the prototyp for the "class"
List. The for loop may look a bit unusual but using this syntax makes it very easy to extend Io to you liking. You do not like the provided if then just write a new one, and the same was done for the 'for' loop here.
I introduce a new variable at the beginning (firt an i) then I wrote
size - 1 this means in fact the same as if I'd written self size - 1 but because we're in the List anyway this means that we'd call the size method on a list. Io is a prototyp based language, getting a new derived object is hardly recognicable. If I'd not like to add the sort the List I could have written:
MyList := clone List MyList bubbleSort := .....
and then I have a new object derived from List but with an additional bubbleSort. There is not need on syntacic sugar. Just write it down and you have it.
But now back to the algorithm, I have another loop in the first loop starting the next parameter after 'size -1' is 0, that's the end condition so I iterate from the last element to the first element. Now we have to get the "bubbling" for that we use another loop this time with the loop variable j from 0 up to i. Please remember that the outer loop runs from the end of the list to the first element in the list. this explains the next if .
if ((cmpBlock call...
This way a closure is called in Io. If you'd the same in Smalltalk you'd use something like codeblock value.... But now let's see what happens if we do a comparisn of a(i=6) = 24 and a(j=0) = 1 with the comparison <.
The question is: 'if 24 < 1' then
swapIndices(j,i)
swapIndices does the exchange. Quite handy wouldn't you agree ;-)
So after we have looped through them all we hopefully have sorted the array. Let's see:
tList := list (1,-2,-3,10,100,-23, 24)
tList bubbleSort(block(a,b, a < b))
write ("tList bubleSorted = ", tList, "\n")
Output:
tList bubleSorted = list(-23, -3, -2, 1, 10, 24, 100)
That's very fine, now if we feel that we'd like to sort something else, we simply can give bubbleSort another comparisonFunction and that's it. Closures and blocks are so handy, it's hard to believe that any language can survive without such thing....