Sort Demo 1.0

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



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

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

Build Instructions

Pre-Requisites

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).

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.

Copyright © 2011 by Big Bad Bob Frazier, all rights reserved.