++ This sounds like a CHALLENGE! :-)
Below is a *real* challenge, for all those in net land with extra time
on their hands during easter and spring break! I've included below a
very efficient sorting routine, together with a nifty
`sort-program-correctness-tester.'
======================================================================
Your challenge, should you wish to accept it,
is to write a faster, pseudo-portable, and correct
sort routine that fulfills the same specification
as the one included below.
======================================================================
Pseduo-portable is eclectically defined as ``compiling and executing
correctly with GNU GCC, AT&T cfront, and GNU G++!'' Actually, K&R C is
fine too, I just didn't feel like cluttering up my program with
#ifdef's everywhere.... The point here is to emphasize creating a
clever algorithm, without being overly dependent on the machine or
compiler. When I compare the final entries, I will use GCC, with the
-O and -fstrength-reduce options enabled.
To make this interesting, assume that the input sizes to the supplied
driver program are: 100,000, 500,000, and 1,000,000
Here are the my results on a Sun 4/260, using G++ 1.34.2 with -O
----------------------------------------
sorttest 100000
time = 1.530
sorttest 500000
time = 8.820
sorttest 1000000
time = 19.130
----------------------------------------
Naturally, not everyone has a Sun 4 ;-). So to make this fair I'll
collect entries, time them on an otherwise empty Sun 4/260, and report
the results. Naturally, I'd be interested in seeing how your programs
perform on other machines, too. If anyone feels that the rules aren't
clear enough, feel free to elaborate them. I'm mostly interested in
seeing whether anyone can beat the following sorting algorithm for
large input values.
If enough people enter good programs, I'll archive them and make
them available for anonymous FTP.
Good luck!!!
Doug
---
On a clear day, under blue skies, there is no need to seek.
And asking about Buddha +------------------------+
With loot in your pocket. | office: (714) 856-4043 |
----------------------------------------------------------------------
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: checksort.c sort.c test.c Makefile
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'checksort.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'checksort.c'\"
else
echo shar: Extracting \"'checksort.c'\" \(3067 characters\)
sed "s/^X//" >'checksort.c' <<'END_OF_FILE'
X/* Efficient and general mechanism for testing correctness of sort routines.
X Please excuse the lack of comments. I wrote this long ago, before
X learning the importance of documentation (the hard way!) ;-). */
X
Xtypedef struct node
X{
X int item;
X struct node *next;
X} node;
X
Xint *range_buf;
Xnode **hash_buf;
Xint buf_size;
Xnode *mem_stack;
Xnode *stack_top;
Xnode sentinel;
Xnode *sentinel_ptr = &sentinel;
X
Xint
Xfree_mem_and_exit(int status)
X{
X free (mem_stack);
X free (hash_buf);
X free (range_buf);
X return status;
X}
X
Xint
Xinit_hash_buf (void)
X{
X register int i;
X
X if (!(hash_buf = (node **) malloc (buf_size * sizeof (node *))))
X return 0;
X
X for (i = 0;i < buf_size;i++)
X hash_buf[i] = sentinel_ptr;
X
X return (mem_stack = stack_top = (node *) calloc (buf_size, sizeof (node))) != 0;
X}
X
Xnode *
Xmake_node (int item)
X{
X node *temp = stack_top++;
X
X temp->item = item;
X return temp;
X}
X
Xint
Xhash_value (int item)
X{
X return item % buf_size;
X}
X
Xvoid
Xhash_insert (int item)
X{
X int loc = hash_value (item);
X node *new_node = make_node (item);
X
X new_node->next = hash_buf[loc];
X hash_buf[loc] = new_node;
X}
X
Xint
Xremove_node (int item)
X{
X int loc = hash_value (item);
X node *temp = hash_buf[loc];
X node *prev = 0;
X
X for (sentinel.item = item; temp->item != item; prev = temp, temp = temp->next)
X ;
X
X if (temp == sentinel_ptr)
X return 0;
X else if (!prev)
X hash_buf[loc] = temp->next;
X else
X prev->next = temp->next;
X
X return 1;
X}
X
Xint
Xdelete_buf(int *base)
X{
X int i;
X
X for (i = 0; i < buf_size; i++)
X if (!remove_node (base[i]))
X return 0;
X
X for (i = 0; i < buf_size; i++)
X if (hash_buf[i] != sentinel_ptr)
X return 0;
X
X return 1;
X}
X
Xint
Xcheck_sort (int *original, int *base, int size)
X{
X int range = base[size - 1];
X
X if ((buf_size = size) >= range)
X {
X if (!(range_buf = (int *) calloc (range, sizeof (int))))
X return -1;
X else
X {
X int i;
X
X for (i = 1; i < buf_size; i++)
X if ((base[i] < base[i - 1]) || base[i - 1] > range || base[i - 1] < 0)
X return free_mem_and_exit (0);
X else
X ++range_buf[base[i - 1]];
X
X ++range_buf[base[buf_size - 1]];
X
X for (i = 0; i < buf_size; i++)
X if (range_buf[original[i]] <= 0)
X return free_mem_and_exit (0);
X else
X --range_buf[original[i]];
X
X for (i = 0; i < range; i++)
X if (range_buf[i] != 0)
X return free_mem_and_exit (0);
X
X }
X }
X else if (!init_hash_buf ())
X return -1;
X else
X {
X int i;
X
X for (i = 1; i < buf_size; i++)
X {
X if (base[i] < base[i - 1])
X return free_mem_and_exit (0);
X else
X hash_insert(base[i - 1]);
X }
X
X hash_insert (base[buf_size - 1]);
X if (!delete_buf (original))
X return free_mem_and_exit (0);
X }
X return free_mem_and_exit (1);
X}
END_OF_FILE
if test 3067 -ne `wc -c <'checksort.c'`; then
echo shar: \"'checksort.c'\" unpacked with wrong size!
fi
# end of 'checksort.c'
fi
if test -f 'sort.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'sort.c'\"
else
echo shar: Extracting \"'sort.c'\" \(5893 characters\)
sed "s/^X//" >'sort.c' <<'END_OF_FILE'
X#include <stdio.h>
X#include <ctype.h>
X
X/* the next 5 #defines implement a very fast in-line stack abstraction */
X
X#define MAKE_STACK(S) ((stack_node *) malloc (sizeof(stack_node) * (S)))
X#define PUSH(LOW,HIGH) do {top->lo = LOW;top->hi = HIGH;top++;} while (0)
X#define POP(LOW,HIGH) do {--top;LOW = top->lo;HIGH = top->hi;} while (0)
X#define STACK_NOT_EMPTY (stack < top)
X#define SWAP(A,B) do {int _temp = (A);(A) = (B);(B) = _temp;} while (0)
X
X/* Discontinue quicksort algorithm when partition gets below this size.
X This particular magic number was chosen to work best on a Sun 4/260. */
X#define MAX_THRESH 15
X
X#ifdef __GNUG__
X#define MAX(X,Y) ((X) >? (Y))
X#else
X#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
X#endif
X
X/* Data structure for stack of unfulfilled obligations. */
Xtypedef struct
X{
X int *lo;
X int *hi;
X} stack_node;
X
X/* Once main array is partially sorted by quicksort the remainder is
X completely sorted using insertion sort, since this is efficient
X for partitions below MAX_THRESH size. BASE points to the beginning
X of the array to sort, and END_PTR points at the very last element in
X the array (*not* one beyond it!). */
X
Xinline static void
Xinsert_sort(int *base, int *end_ptr)
X{
X int *run_ptr;
X int *tmp_ptr = end_ptr;
X int *thresh = MAX (base, end_ptr - MAX_THRESH);
X
X /* Find the smallest element in the first threshold and put it at the
X end of the array. This is guaranteed to be the smallest element in
X the array, and it speeds up the inner loop of insertion sort. */
X
X for (run_ptr = tmp_ptr - 1; run_ptr >= thresh; run_ptr--)
X if (*run_ptr > *tmp_ptr)
X tmp_ptr = run_ptr;
X
X SWAP (*tmp_ptr, *end_ptr);
X
X /* Typical insertion sort, but we run from the `right-hand-side'
X downto the `left-hand-side.' */
X
X for (run_ptr = end_ptr - 1; run_ptr > base; run_ptr--)
X {
X int temp = *(tmp_ptr = run_ptr - 1);
X
X /* Select the correct location for the new element,
X by sliding everyone down by 1 to make room! */
X
X while (temp > *++tmp_ptr)
X tmp_ptr[-1] = *tmp_ptr;
X
X tmp_ptr[-1] = temp;
X }
X}
X
X/* Return the median value selected from among the
X LOW, MIDDLE, and HIGH. Rearrange LOW and HIGH so
X the three values are sorted amongst themselves.
X This speeds up later work... */
X
Xinline static int
Xfind_pivot(int *low, int *high)
X{
X int *middle = low + ((high - low ) >> 1);
X
X if (*middle < *low)
X SWAP (*middle, *low);
X if (*high < *middle)
X SWAP (*middle, *high);
X else
X return *middle;
X
X if (*middle < *low)
X SWAP (*middle, *low);
X
X return *middle;
X}
X
X/* Order elements using quicksort. This implementation incorporates
X 4 optimizations discussed in Sedgewick:
X
X 1. Non-recursive, using an explicit stack of log (n) pointers that
X indicate the next array partition to sort.
X
X 2. Choses the pivot element to be the median-of-three, reducing
X the probability of selecting a bad pivot value.
X
X 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
X insertion sort to sort within the partitions. This is a
X big win, since insertion sort is
...
read more »
binary stdin/stdout