Image via Wikipedia
As a rule, I avoid technical (Computer Science) posts in this blog. Such posts normally appear in my other (professional) blog, http://prologsource.wordpress.com. This time, however, I make an exception. There is something very important, I think; which (if presented in a simple way) is not incomprehensible by people who are not professional programmers or Computer Scientists:
It’s about a New Sorting Algorithm, called «Tourist Sort», which is probably *the* (or at least one of the) Fastest in the world…
To be sure, this new clicking HERE.was tested quite thoroughly, timed very precisely and compared repeatedly with many other extremely fast Sorting Algorithms. To verify this claim, you can download a demo of «Tourist Sort» by
Here are some screen-shots from the (downloadable) Demo, compressed as a GIF:
The demo consists of an executable file («TOURISTS.EXE») a brief «README.txt», an Error explanations data file (e.g. if your PC has insufficient RAM memory), and -finally- a log0file with extensive timing statistics from my PC (a Dual Core with 3 Gigabytes of RAM).
- DISCLAIMER: I’d be very wary of claiming with 100% certainty, that «Tourist Sort» actually IS THE «fastest in the world», since new sorting algorithms do emerge often, sometimes also winning prizes for being astonishingly faster than all their predecessors…
The demo is very simple, but sufficient to test «Tourist Sort» using a variety of user-generated random-data files (you can create), comparing it with two other ultra-fast Sorting programs:
- 1) An implementation of «Quick-Sort» in hand-optimized Pure Assembly Language (using code published by the «MASM project 2007«, written by Steve Hutchesson).
- 2) A standard ultra-fast ‘C’ implementation of «Iterative Quick Sort«.
So, if you download the demo and run it, you can check out the validity of my claim that «Tourist Sort» is considerably faster than the fastest of these two (typically 50% faster, sometimes twice as fast – or more).
As a matter of fact, Steve Hutchesson‘s optimised Assembly language version of Quick Sort (which is compared with Tourist Sort inside the downloadable demo) IS WAS probably the fastest in the world, till now… (…or at least it was among Open Source sorting projects).
There do exist faster sorting programs than this, but they tend to assume other advantages (e.g. parallel operation in special hardware). Therefore (if these considerations are correct) it is reasonable to assume that Tourist Sort is the (new) fastest algorithm, at the present time.
Why was this algorithm named «Tourist Sort«?
Well, just as «Postman Sort» was named «Postman-« because its operation resembles the way parcels are sorted and delivered by postmen, «Tourist Sort» reminded me of the way…. tourist reservations are done by Travel Agencies, i.e.
-Instead of dealing with each tourist, individually, group-reservations are made for several tourists at once, before any tourists arrive in their destinations (and so on). Now, although this «tourist reservation analogy» is naive, simplistic, as well as theoretically flawed (to some extent), it is -probably- a useful visual hint for understanding Tourist Sort’s basic idea of operation:
- In the «Tourist Sort» algorithm (an unusual descendant of Bucket Sort and Radix Sort) nothing is (actually) ever compared with anything.
- Forget about conventional sorting methods, forget about shuffling things around using comparisons, forget -finally- «N*Long N complexities», too…
TOURIST SORT is of LINEAR (or quasi-linear) Time-complexity, i.e. «order of N times a constant».
Tourist Sort is -however- a very unusual Algorithm (most probably a new family of Sorting Algorithms) with strong resemblances as well as strong differences with other known (rare) linear-time- sorting Algorithms. (They DO exist – you know, mine is NOT the only one…) Tourist Sort» (like «Postman Sort») belongs to a rare category of sorting algorithms that do not involve item-comparisons (e.g. lexicographic) of any kind. More details about this new algorithm’s exact operation will be posted -hopefully- in my other (technical) blog, in the near future.
Tourist Sort’s History:
Tourist Sort arose out of creative experimentations with sorting methods, about a decade ago. At that time, it was implemented (rather inefficiently) in Visual Prolog. It took some years, before a working, optimised Assembly Language implementation became possible. The basic algorithm was then briefly presented in a Computer Science conference (the ALC Visual Prolog Conference) in Portugal, in April 2006. At that time, exhaustive comparative tests (performed in the offices of a company who can verify this claim) proved that “Tourist Sort” is indeed (slightly) faster than “Postman Sort”, which was a well known winner in Sorting Algorithm Speed Competitions: “Postman Sort” was proved to be the fastest Sorting Algorithm in the world, at that time. However, a year later, it was officially announced that someone else’s Sorting Algorithm had won the Annual Sorting Contest (a Chinese algorithm, in fact). (Stay tuned for more news about all this, and about Tourist Sort’s place -or purpose- in the “Sorting Contest” scene…)
- A hilarious Greek blog-story: A few months ago, a Greek blogger called «McManus» took the… piss out of my CV(!) laughing his head off, after reading there certain… wild claims I made about «Tourist Sort» (and other… strange innovations); he simply thought I was fooling around, more or less.
- Well, I decided it’s about time that such (private) work is presented in a much better way, as well as made more open to public scrutiny and verification. Besides:
ALL information (including new algorithms) wants to be free! 🙂
Image via Wikipedia
Some last-minute Technical tips and notes:
- When running the Tourist Sort Demo, Please avoid data-files larger in size than your RAM memory (and other factors) allow. (I haven’t yet implemented the best possible use of available RAM). In my machine, files up to about 100 Megabytes are sorted OK (with occasional crashes if there are too many other windows and programs open at the same time).
- This new version of (2008-) Tourist Sort is about 25-35 % faster than the one of 2006. although I haven’t worked much on improving it, because of other projects, obligations, and… blogomania. 🙂 This (small but significant) speed increase arose from rewriting in optimised Assembly Language large parts of the algorithm that had been previously left in their original form, implemented in Visual Prolog (e.g. repeated applications of «Retract»/»Assert» commands).
Tourist Sort and Postman Sort:
Although Robert Ramey’s «Postman Sort» is a work of art (as well as THE fastest Sorting Algorithm in the World, till a few years ago), and although Tourist Sort has some strong similarities with it, Tourist Sort is NOT Postman Sort; it is also very different, a new Sorting Algorithm, which… I promise to elucidate in the near future, in every detail (after a period of years during which -hoping to make money from it just like Ramey- I kept the algorithm a secret).
- Unfortunately, I was unable to run my copy of «Postman Sort», to check out if Tourist Sort is still faster than Postman Sort, since my shareware licence expired. However, this will certainly be done in the near future. (Two years ago, the test was performed several times, proving that Tourist Sort was faster – in a friendly company’s offices).
- However, my strong feeling is that BIG improvements in Tourist Sort’s execution speed haven’t even begun; I expect a further 5-10 times speed-increase, just by rewriting crucial parts of Tourist Sort in SSE-2 SIMD (Single-Instruction-Multiple-Data) Extended Assembly Language instructions, valid in Pentium 4 and Multi-Core CPUs.
- Amusingly enough, the 2006-version of Tourist Sort would probably fail to beat Postman Sort today, if Postman Sort had been (in the meantime) re-written in optimised Assembly language.
- Tourist Sort was faster than Postman, back in 2006, mainly because Postman- was implemented in ‘C’ rather than Assembly. (I have no idea how P.S. is implemented today, but my strong guess is Assembly).
- Tourist Sort is also IDEAL for Parallel Computing; So ideal in fact, that most of the time the algorithm repeatedly (and wastefully) does in one CPU lots of tasks that are ALREADY completely independent, distributed, as pieces of cake for several, parallel CPUs!
Related articles by Zemanta
- Has there been any innovation in Computer Science in the last decade?
- Back to Basics: Algorithms
- US computer science drought may be bottoming out
- Bacteria colonies used to model parallel processing system
- reading/writing/sorting Prolog variables, using the original variable-names (LPA Prolog code)
- Assembly Language for Visual Prolog Meta-programming