Tourist Sort (a new sorting algorithm) -is it really THE fastest? (Νέος Αλγόριθμος Ταξινόμησης – άραγε *O* Γρηγορότερος;)

A recursive merge sort algorithm used to sort ...

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 algorithm 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 clicking HERE.

Here are some screen-shots from the (downloadable) Demo, compressed as a GIF:

Screen shots of the Tourist Sort Demo
Screen shots of the Tourist Sort Demo

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!🙂

Photographed by Liam AdlenImage 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!
Reblog this post [with Zemanta]

4 comments

  1. Χεχε…

    Είναι πολλά τα πορτοκάλια αυτής της… πορτοκαλιάς, αγαπητέ μου Ζορμπά, «άτυποι Ολυμπιακοί αγώνες» μιλάμε..

    Το πρόβλημα είναι ο καλύτερος τρόπος να ταξινομηθεί αλφαβητικά (όπως οι λέξεις ενός λεξικού) ένα αρχείο π.χ. κατάλογος λέξεων ή αριθμών. Μάλιστα… ΠΑΛΙ καλά που δεν ισχυρίζομαι ότι είναι (απαραίτητα) η δική μου μέθος «Η» γρηγορότερη γιατί κάθε χρόνο βγαίνουν κι άλλες, ολοένα και πιο γρήγορες.

    Η «τουριστική ταξινόμηση» έχει πολλή πλάκα και στη θεωρία. Είχα μάλιστα κάποτε διανθίσει τον κώδικά μου με σχόλια όπως… «Μέτρημα Τουριστών», «Κλείσιμο Δωματίων», «Αποστολή Τουριστών», κλπ.

    Χθες μια φίλη μου βρήκε ΑΛΛΟΝ έναν «υποψήφιο», που όμως.. ενώ πήρε και πατέντα από το Αμερικάνικο κράτος (Patent Office) τελικά… αντέγραψε κομμάτια των ιδεών κάποιου άλλου, ενώ παραπλανά ότι δήθεν δεν είναι η δική του μέθοδος «σπάταλη σε μνήμη». ΤΡΙΧΕΣ, η μέθοδός του σπαταλάει ΠΟΛΛΑΠΛΑΣΙΑ μνήμη από τα ίδια τα δεδομένα.

    Τουλάχιστον εγώ… είμαι ειλικρινής, δηλαδή
    1) Παραδέχομαι ότι η μέθοδός μου περιέχει και στοιχεία από άλλες (Radix Sort, Postman Sort, – περισσότερα εν καιρώ).
    2) Δεν λέω ότι είναι 100% καινούργια αλλά ότι αποτελεί καινοτομία. (Πάντως πατέντα δεν ζήτησα..)
    3) Δεν λέω ότι «δεν σπαταλάει μνήμη». Σπαταλάει λίγο πιο πολλή από διπλάσια, των ίδιων των δεδομένων.

    Περισσότερα (ΚΑΙ εκλαϊκευτικότερα) εν καιρώ…🙂

  2. @Βασιλική
    Λυπάμαι αλλα λέω ΠΟΛΥ αυστηρά και εμφατικά 100% ΟΧΙ σε ΟΛΑ τα ποδοσφαιρικά. ΔΕΝ ασχολούμαι, ΔΕΝ υποστηρίζω ΚΑΜΙΑ ποδοσφαιρική ομάδα και (έτσι) εξοικονομώ πολύ χρόνο για άααλλα πράματα…

    Τώρα…
    ΓΙΑΤΙ «όχι remix στον Θεοδωράκη»;
    Μάλλον _δεν_ κατάλαβες καλά. Ο ΠΡΩΤΟΣ που συμφώνησε με τα (συγκεκριμμένα) remix, αφού μάλιστα τα ΑΚΟΥΣΕ, είναι ο _ίδιος_ ο Μίκης Θεοδωράκης, ήδη από το 2006. Η σκαναρισμένη δική του συστατική επιστολή (υπέρ των remix) βρίσκεται σε παλιό ποστ αυτού του blog, αλλά και εδώ:

    Στην πραγματικότητα, το ΠΕΡΙΒΑΛΛΟΝ του Μίκη αντιδρά (κατά πάσαν πιθανότητα) σε αυτή την προσπάθεια, η οποία γι’ αυτό το λόγο «κόλλησε»,εδώ και καιρό. Επανειλλημένες προσπάθειες να μιλήσω με «δικούς του ανθρώπους» που θεωρεί «πιο αρμόδιους» (από τεχνική άποψη) κόλλησαν στην επίμονη σιωπή τους. Κι αυτό σε αντίθεση με τον ΙΔΙΟ το Μίκη, με τον οποίο συναντήθηκα δύο φορές (και επί σειρά μηνών αντάλλαξα και πολλά e-mail μέσω της γραμματέως του).

    Δυστυχώς, έχω -βέβαια- και άλλες δουλειές. Ε, κάποια στιγμή… κουράστηκα να «κυνηγώ» τους ανθρώπους του Μίκη, παρά τις επανειλλημένες δικές του ενθαρρύνσεις να συνεχίσουμε.
    Τα συγκεκριμμένα remix, τέλος, δεν είναι απλά remix αλλά «remake». Δηλαδή περιέχουν και εντελώς νέες παραλλαγές μελωδιών, ενώ καθιστούν τη μουσική του Μίκη κατάλληλη για χορευτικά Club σε ΟΛΟ ΤΟΝ ΚΟΣΜΟ… (σε μια εποχή που ελάχιστοι τον ακούνε εκτός Ελλάδος, να μην πω και εντός…)

    Τα λέω όοολα αυτά, γιατί… νιώθω πίκρα και οργή για τα χάλια αυτής της χώρας, που ΠΑΝΤΑ τρώει και ΠΑΝΤΑ σαμποτάρει τα _ίδια_ τα παιδιά της (ΚΑΙ παραλίγο τον ίδιο το…, Μίκη κάποτε). Πάντως, επειδή ο ίδιος ο Μίκης μερικές φορές πληροφορείται όσα γράφω στο μπλογκ, μέσω της Ρένας (της γραμματέας του), ας μάθει ότι _δεν_ έπαψα να τον εκτιμώ, να είμαι έτοιμος να προχωρήσουμε, κ.ο.κ.
    …Αλλά ΔΕΝ μπορώ να το κάνω εντελώς μόνος μου (το σχόλιό σου είναι ΑΠΛΟ δείγμα της ΑΝΤΙΔΡΑΣΗΣ που συναντάω)…

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s