Abstract
Robsort in a
GNU public license
sorting algorithm devleloped by
Robert Thompson.
Robsort uses random number generation to sort arrays of integers. It is claimed to be the world's
least efficient sorting algorithm. Scientists have calculated the robsort algorithm to approach an
order of [n!] (n factorial) inefficiency, however this inefficiency could only theoretically be
obtained by using truly random numbers. The Robsort source code is an implemenation/demonstration
of this algorithm for both UNIX and Windows machines.
5/27/03 - It has been brought to my attention that a similarly inefficient O[n!] sorting algorithm
was possibly in existence before Robsort, for more information goto the
Bogosort homepage. An implementation of Bogosort can
be found here, however unlike Robsort, this implementation of Bogosort does
not appear to be multi-threaded and will only use one processor.
Download Robsort
robsort v1.0 *NIX source
robsort v0.86 Windows 9x/NT/2000 binary
robsort is featured on sourceforge
robsort is also featured on freshmeat
Robsort Q&A
How does robsort work?
-
Robsort reads an array of integers and randomly arranges the order of those integers. It then checks to
see if the array is sorted, if the array is sorted, robsort has done its job. If the array is not sorted,
robsort ranomizes the array again. It continues this process untill it successfully sorts the array.
Why would I use robsort instead of some other more efficient sorting algorithm?
-
Because robsort is more inefficient.
Scientists who study inefficiency
use robsort to prove specific aspects of number theory. Robsort is used as a benchmark for measuring
algorithm efficiency, it is the benchmark by which all other sorting algorithms are measured.
Why is robsort GNU software?
-
Although the science behind robsort is obviously patentable,
Robert Thompson
has chosen the GNU public license because he holds that this technology is universal and
should be "owned" by the general public. Also, Robert wants to make robsort available for educational
and research purposes without financial barriers.
When I try to run robsort, I get the message: Segmentation Fault (core dumped)?
-
In an effort to maintain maximum inefficiency, robsort often produces this message. This is
not an error, rather it is a message stating that the operating system has dumped its memory and register
contents to disk for the purposes of debugging. It usually means that the computer robsort is being run on
cannot handle robsort.
Scientists who use robsort
analyze the 'core' files whic h are produced to determine which hardware upgrades are necessary to
properly run the application.
How long does robsort take to sort integers?
-
Since robsort nears order n factorial inefficiency, the amount of time required to sort an array depends
drastically on the siz e of the array. Start with a small number of integers, say around 9, and work up.
There is no limit, however scientists hav e currently been unable to sucessfully sort 17 or more
integers using robsort due to its incredible inefficiency.
Does robsort utilize multiple processors?
-
Yes, robsort is written with POSIX threads support. Lightweight robsort processes are automatically
distributed to free processors by the operating system. Threads allow robsort to inefficiently use all
available processors. The Windows 9.x/NT/2000 version of robsort does not currently support threads.
How do I tell robsort what integers I want to sort?
-
Place the integers you wish to robsort in a file called sortdata.txt. sortdata.txt must contain 1
line of integers with spaces seperating them and it must be located in the same directory as the
robsort binary.
|