Sequential Algorithms: Improved Probabilistic Integer Sorting
This page includes the code used in the experiments described
in the paper: A. V. Gerbessiotis and C. J. Siniolakis. ``Probabilistic
Integer Sorting'' that has been submitted for publication and also
available on the Web in preliminary form in the Publications section of
this web-page. The code includes an implementation of our algorithm,
an implementation of HybridSort(MacLaren66,Meijer and Akl80,
and Hagerup89), and an implementation of RadixSort for strings.
We provide some support for testing these functions against each other
and also to the native qsort function (just for control purposes).
If you plan to use our testing environment note that timings through the
clock() function call may not be very accurate. Somehow we could get more
accurate timing results be utilizing the facilities of the bsp_time() function
of BSPlib{}, a parallel programming library. Note that there is nothing
inherently parallel in our supplied code.
- tars/503v6.tar
Current Version of sequential code for probabilistic integer sorting.
An implementation of HybridSort, and RadixSort for strings is also
available.
Untar tar file, read copyright notice in file copyright
and file 503.txt for instructions.
- tars/BSPsun.tar
A tar ball of BSPlib version 1.4, installed and compiled on
a Sunl Ultra 10 platform. Tar xvf it locally, and it will untar in a directory
named BSP. Make sure you include in your path ~/BSP/bin assuming that you
untarred it at the root of your home directory.
- tars/BSPlinux.tar
A tar ball of BSPlib version 1.4, installed and compiled on
a RedHat 9.0 PC platform. Tar xvf it locally, and it will untar in a directory
named BSP. Make sure you include in your path ~/BSP/bin assuming that you
untarred it at the root of your home directory.
- tars/v1.4_bsplib_toolset.tar
A tar ball of BSPlib version 1.4. If you tar xvf it, it will create
a directory BSP. Follow directions in BSP directory to install it.
Compilation and linking won't take more than few minutes.
Last Update: January 4, 2004