In a message dated 02-05-98, Mathieu Bouchard said to Jonathan de Boyne
Pollard about Sort Algorithm
Hi Mathieu,
JdBP> use Comb Sort. It's reasonably fast, and it is
MB>what is the comb sort? and Batcher's algorithm? (in short... just the
MB>algorithms in pseudocode, details are ok but not necessary)
Since Jonathan has not answered you I shall provide some info.
Batcher's algorithm is rather complex, but it is capable of performing many
of its functions in parallel. The best reference for it is, of course,
Knuth. It is best coded in assembler, since one would normally use this
algorithm for consistently high speed sorts and it works best when the
underlying CPU hardware is exploited fully.
I'm not sure what Jonathan meant by 'comb sort', but I _think_ he means
Donald Shell's algorithm. Since pseudo-code is [rightly] off-topic in the
C++ echo, here is something far more useful: an implementation of Shell's
algorithm and Hoare's algorithm as C++ templates.
=========================== shellsrt.hpp ===================================
// Templates for Shell's algorithm for ascending & descending sort.
// Copyright (C) 1998, David W. Noon
// All rights reserved.
// You may use this code freely. You may also distribute it, provided
// no charge is levied beyond that for its distribution medium.
// The author makes no warranty of the code's usefulness for any purpose,
// and accepts no responsibility for any damages caused by its misuse.
template void ascending(T array[], int n)
{
int h, i, j, t, const mul = 3;
T Hold_it_here;
if (n > 1)
{
h = mul + 1;
while (h <= n)
h = h*mul + 1;
do
{
h /= mul;
for (i = h; i < n; ++i)
{
Hold_it_here = array[i];
j = i;
for (t = j - h; array[t] > Hold_it_here; t -= h)
{
array[j] = array[t];
j = t;
if (j < h)
break;
}
array[j] = Hold_it_here;
}
} while (h > 1);
}
}
template void descending(T array[], int n)
{
int h, i, j, t, const mul = 3;
T Hold_it_here;
if (n > 1)
{
h = mul + 1;
while (h <= n)
h = h*mul + 1;
do
{
h /= mul;
for (i = h; i < n; ++i)
{
Hold_it_here = array[i];
j = i;
for (t = j - h; array[t] < Hold_it_here; t -= h)
{
array[j] = array[t];
j = t;
if (j < h)
break;
}
array[j] = Hold_it_here;
}
} while (h > 1);
}
}
============================== quicksrt.hpp ================================
// Templates for Hoare's algorithm for ascending & descending sort.
// Note that this is Hoare's original, recursive algorithm. You might
// care to apply Sedgewick's modifications to remove recursion.
// Copyright (C) 1998, David W. Noon
// All rights reserved.
// You may use this code freely. You may also distribute it, provided
// no charge is levied beyond that for its distribution medium.
// The author makes no warranty of the code's usefulness for any purpose,
// and accepts no responsibility for any damages caused by its misuse.
template void ascending(T array[], int l, int r)
{
int i, j;
T Hold_it_here, Split_value;
if (r > l)
{
Split_value = array[r];
i = l - 1;
j = r;
do
{
do
{
++i;
} while (array[i] < Split_value);
do
{
--j;
} while (array[j] > Split_value);
Hold_it_here = array[i];
array[i] = array[j];
array[j] = Hold_it_here;
} while (j > i);
array[j] = array[i];
array[i] = array[r];
array[r] = Hold_it_here;
ascending(array,l,i-1);
ascending(array,i+1,r);
}
}
template void descending(T array[], int l, int r)
{
int i, j;
T Hold_it_here, Split_value;
if (r > l)
{
Split_value = array[r];
i = l - 1;
j = r;
do
{
do
{
++i;
} while (array[i] > Split_value);
do
{
--j;
} while (array[j] < Split_value);
Hold_it_here = array[i];
array[i] = array[j];
array[j] = Hold_it_here;
} while (j > i);
array[j] = array[i];
array[i] = array[r];
array[r] = Hold_it_here;
descending(array,l,i-1);
descending(array,i+1,r);
}
}
============================== sorttest.cpp ================================
// Program to test sort routines
#include
#include
#include
#include
// Include the templates for ascending & descending sort
namespace Shell
{
#include "shellsrt.hpp"
}
namespace Hoare
{
#include "quicksrt.hpp"
}
int main()
{
int i;
int rand_array[200];
cout << "Shell sort\nUnsorted array:\n";
for (i = 0; i < 200; ++i)
{
rand_array[i] = rand(); // 16-bit! Yuck!!
cout << '\t' << rand_array[i] << '\n';
}
Shell::ascending(rand_array,200);
cout << "\n\nAscending array:\n";
for (i = 0; i < 200; ++i)
cout << '\t' << rand_array[i] << '\n';
Shell::descending(rand_array,200);
cout << "\n\nDescending array:\n";
for (i = 0; i < 200; ++i)
cout << '\t' << rand_array[i] << '\n';
cout << "\n\nQuicksort\nUnsorted array:\n";
for (i = 0; i < 200; ++i)
{
rand_array[i] = rand(); // 16-bit! Yuck!!
cout << '\t' << rand_array[i] << '\n';
}
Hoare::ascending(rand_array,0,199);
cout << "\n\nAscending array:\n";
for (i = 0; i < 200; ++i)
cout << '\t' << rand_array[i] << '\n';
Hoare::descending(rand_array,0,199);
cout << "\n\nDescending array:\n";
for (i = 0; i < 200; ++i)
cout << '\t' << rand_array[i] << '\n';
return 0;
}
============================================================================
You will need a fairly recent C++ compiler to deal with the namepsaces, or
you can split up the test program to run the algorithms separately. I used
Watcom C/C++ 11.0 for my testing last night.
To All:
=======
Note that Hoare's algorithm is the one used by the qsort() subroutine of the
Standard C Library. You might care to benchmark some template instances
against the library call. Also give Shell's algorithm a run against qsort(),
especially on data that are already almost ordered. Moreover, you can
benchmark all these against Michael Rathburn's bubble sort (posted earlier,
in this echo) and see who wins. Please post your test program(s) (but not
re-post these templates) and the results here.
Remember what Benjamin Disraeli said, albeit presciently, about computer
benchmarks:
"There are three kinds of lies: lies, damned lies and statistics."
Regards
Dave
___
* MR/2 2.25 #353 * MAC error msg: "Like dude, something went wrong"
--- Maximus/2 3.01
---------------
* Origin: DoNoR/2,Woking UK (44-1483-717905) (2:440/4)
|