Resort to sort

So the past few days I've been playing around with some simple algorithms. I'm not 'professionally' trained, and most of my experience has been with what I've seen in code or have implemented myself. Does that make me less of a developer for not being classically trained? Maybe, maybe not.

In particular I've been playing around with some of the sorting algorithms. Stuff like Bubble sort, Selection sort, Insertion sort, and of course Quicksort.

My first task as been to study the algorithm and look at whatever pseudo-code or explanation is presented for the algorithm. Study and understand it. Then is to walk away from any computer or anything, take a little break. After a short time I then pull out a pen and paper and write down a Dart version of the code. I write it out in front of me without referring to APIs, or without referencing the material.

I later then enter that code (or re-write it) into the Dart editor in a simple test file I have. I run it, fix my bugs, and run it again. My test file contains all of the various sorts as I learn them, it then prints out the sorted list and the time it took to complete (using a Stopwatch). I also have a function to create a list of X size filed with values from Random.nextInt.

Being able to easily create a random list of a determined size is nice, as it allows me to easily increment the list size as I choose and see the differences in performance. For instance it took a list of almost 5000 items for Quicksort with the two isolates to be faster than the main-thread version of Quicksort. (See Edit note below)

Many of the algorithms I've implemented are without performance improvements and are far from the most efficient versions available. One thing I've noticed though is List.sort((a, b) => a - b); has generally been one of the best performing algorithms, in lists of up to 10,000 items.

However as I mentioned none of the algorithms has been tuned for best performance or memory usage and are just the 'simple' versions of the algorithms just for my own learning purposes and less for actual performance comparisons. The performance comparisons are more of a visual reference to the Big O Notation for myself.

[Edit:]So I was wrong. I had poorly implemented my Quicksort with Isolates. Very poorly. It was a hodgepodge of Futures and a custom callback. I went through and cleaned it up and changed it so it returned a Future instead of calling a callback. Once I did that I saw an over 10x speed increase in the Quicksort with Isolates version and it and was about the same speed as the Main-threaded Quicksort for lists below 500 items. And faster for lists greater than 500 items. This has more to do with my unfamiliarity with Isolates than with the algorithms themselves.[/Edit]

For those who may be interested, you can the current version of the file here: https://github.com/butlermatt/sorting_dart. As time goes by, I will be adding more algorithms (with comments) as I learn them myself. Again please recall these are not optimized in any way and are only presented as-is, as proof of concept.
In time I may add some optimized versions of algorithms myself as I progress. Keep in mind however this is primarily a learning project and not designed for use. They may be (and are) buggy.

A List of Errors.

Before I get started on this post on Lists (actually, I already started it yesterday but didn't complete it yet ;), I did want to share the information that Seth Ladd recently shared regarding the Dart issue tracker. Sometimes it can be hard to locate or you just can't recall the location to access the tracker. Well never fear! There is a new redirect URL available to use.

dartbug.com

Redirects to the main issue list.

dartbug.com/new

Redirects to the new issue template.

dartbug.com/1199

Redirects to a specific issue number (in this case 1199, the one I submitted and mentioned in my last blog post).

So I'm continuing with Seth Ladd's series on Dart. Today I'm looking at Lists and Arrays. One particular quote from the post particularly grabbed my attention and interest:

Fun fact: As of 2011-12-22, the word "array" does not appear in the Dart spec.'

This interested me as virtually all languages have arrays and refer to them as such. But sure enough a quick search through the current language spec reveals no results for 'array'. Now, as stated in Seth's blog, Dart arrays are Lists. I found it an interesting point none the less.

Interestingly enough however, the VM does output an error which refers to arrays. But when compiled to Javascript (via frog or dartc) the errors properly reflects 'lists'. First I'll demonstrate the code and error then I'll actually provide some additional comments regarding the code.

main() {
  var list = new List(3); // Create an immutable, or 'non-extendable' list
  list.add(4); // Now try to change it (extend it).
}

This results in the following error:

Unhandled exception:
UnsupportedOperationException: Cannot add to a non-extendable array

But when executed on the dartboard we get the following error:

UnsupportedOperationException: Cannot add to a non-extendable list

It surprises me a little that the VM does specifically reference array whereas the code compiled to Javascript, which does have arrays, correctly references a list. There already exists a couple of bug reports. One which I'll only briefly mention, indicates that the word 'array' should be removed from all internal libraries. The second, which I added a comment to regarding the VM specifically is: Issue 1028. This issue aims to be more encompassing removing references from the Libraries as all references which may become visible.

So you may be wondering why it is that List provides an add method if it just generates an error. Well that's because there are two types of lists. A 'non-extendable' list which is created by passing a size to the constructor, or you can create a list without the optional argument to the constructor which creates an empty list you can extend by adding (or removing) values from. An extendable list can also be created from a list literally such as:

var list = [1, 2, 3];

Note however, that unlike some other languages (such as Ruby), you can not call a method on the List literal. Thus the following is not valid code:

var list = [1, 2, 3].add(4);

You'll receive a warning indicating "expression does not yield a value". But it will compile and run (at least until you try to call a List method on list such as length which will generate a runtime error.

However there is a bug in the add method which I have just discovered. The API for List.add indicates that the return type is 'void' (or no return value). This works as expected in the dartboard (javascript). However in the Dart VM, list.add(value) returns the new size of the list. I have submitted a bug report for it here: Issue 1213.