Sort Demo 1.0

Graphically demonstrating multiple sort methods
including a multi-threaded quick sort algorithm!
Slowest on the left, fastest on the right

Here is a SHORT VIDEO showing a screen capture of the latest version 1.1 of Sort Demo. You can't see the mouse pointer, but I deliberately hovered over the toolbar buttons so that the tooltip text would show up and you'd be able to see what I did.

First I did the threaded quick sort, in 'fast' speed. Then I restored the previous data, and slowed it down so you could see what was happening. Then I sped it back up again, restored the data and ran a regular quick sort (one thread only) so you could see the difference (and what threading did for you). Finally, I ran one of the SLOWEST algorithms, the bubble sort, so you could see why you should avoid it. Incidentally my high school taught 'bubble sort' as the only sort algorithm even mentioned, so when I did 'Der Komputer Kontest' for the regional competition, I was at a serious disadvantage, having NEVER seen ANY other way to sort data, and instead of placing well, I wasn't even in the top 10...

So, TEACHERS, USE THIS IN YOUR CLASSROOMS! And the source is ALWAYS OPEN for EXAMINATION!!!

Anyway, it looks like a lot of hype for a simple application, right?

Well here's where you get it:
sortdemo-1.1.tar.gz
sortdemo-1.0-mfc.zip (Windows 'MFC', older version only)

Build Instructions

Pre-Requisites

A compiler (gcc is probably best)
The source files (see above)
wxWidgets (version 2.6 is what I've targeted) or MS DevStudio 2010 [or later]
a windowing OS to run it on. I've tested FreeBSD and Linux. For windows, it worked when I tried the MFC version...

If you have autotools and want to re-build the configure script, the basic method is to first run 'aclocal', then 'autoconf', and then 'automake'. This should be enough to do it. Otherwise, just use the script I included. It should work for ya.

Configuration (non-windows)

For a Linux or BSD (or similar platform) you'll want to run the 'configure' script in order to build the Makefile. Example:

./configure

In some cases (like FreeBSD) the wxWidgets installation may be set up for multiple versions, and the 'wx-config' application may not have that name. In this case, you'll need to tell configure where to find it, as follows:

./configure --with-wx-config=/usr/local/bin/wxgtk2-2.6-config

In this case, I specified the complete path to the correct wx-config application.

Building (non-windows)

Building is simple. Just type 'make' after running './configure', as

make

You can also use a make target such as 'make install' to install the application into the default location (usually /usr/local/bin or /usr/bin). Make sure you have write access to the destination (and you're not destroying anything) first.

Running

And to run the application, from the build directory type
./sortdemo

Or if you installed it, just 'sortdemo' (assuming it's in the path) or the fully qualified file name, i.e. '/usr/local/bin/sortdemo' .

There's really no help, but if you pop down the 'Sort' menu you'll see several sort options, slowest being 1 and fastest being 8. These correspond to the buttons in the middle of the tool bar. You can use menus or toolbar buttons as you see fit.

NOTE: The 'stop' feature does not work for the multi-thread sort, but you won't need it.

The left-most button generates NEW data, and the next one (the 'magician hat') recovers the previous data (so you can compare methods). In the examples at the top of the web page, the fastest method (multi-thread quick sort) was used. If you were to recover the data and use a different method (such as single-thread quick sort) you can get an idea how they compare. On average the multi-thread quick sort is about 2.5 times faster than the single-thread quick sort. The multi-thread quick sort simulates a 4-core machine, but the bulk of the time is spent on the first iteration (which must be done single-threaded). After that, multiple work units are scheduled, and the rest of the sort goes by VERY quickly since you are sorting several sections simultaneously (instead of just one section at a time).

A *NEW* feature, the 'speed' button (green with 'go' written on it) can toggle the speed at which the sort happens, EVEN WHILE THE SORT IS RUNNING. There is a corresponding menu item for this as well, under 'Sort'. It has a checkbox, and is (by default) set to FAST. This feature is ONLY in the wxWidgets version, however, so for a windows system you would need to build it using wxWidgets. Your Mileage May Vary.

Anyway, have fun, and don't blame me if something goes wrong. This app comes with known bugs and things that may not harm your system, or perhaps they may (use it at YOUR risk, not MINE). It's open source so you can do what you want with it. You may find GPL licensing there, or not (I can't remember right now) and just assume it's public domain unless you see otherwise.

About multi-threaded quick sort

Some multi-threaded algorithms are Embarassingly Parallel in that they are very very easy to implement. An example of that could be a discrete fourier transform (aka DFT). Each 'harmonic' can be independently calculated from the others, and each one requires about the same amount of time to calculate. So the total time to do the calculation is approximately divided by the total number of processors you can devote to it, with one thread dedicated to each harmonic. You could even schedule them ALL in parallel and get just about the same result (up to a point where resource allocation becomes a problem). On the other hand, parallel processing of a quick sort isn't so easy. In fact, all you can really do is schedule "the bottom half" portion as 2 separate threads, each of which could spawn more threads in its bottom half (as needed). This can create SOME scheduling conflicts and dependency issues which I deal with in 'sortdemo' (edge cases, mostly). So it is a good example of an algorithm which isn't 'parallel', but must be divided up into 'work units' that often depend on one another to complete before the process can move forward.