Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!mcnc!ncsuvx!ecemwl!jnh
From: jnh@ecemwl.ncsu.edu (Joseph N. Hall)
Newsgroups: comp.lang.c
Subject: Re: Looking for portable sort algorithm
Keywords: C, sort algorithm, portable, wanted
Message-ID: <3994@ncsuvx.ncsu.edu>
Date: 20 Sep 89 06:14:31 GMT
References: <1102@lakesys.UUCP>
Sender: news@ncsuvx.ncsu.edu
Reply-To: jnh@ecemwl.UUCP (Joseph N. Hall)
Organization: North Carolina State University
Lines: 67

In article <1102@lakesys.UUCP> davek@lakesys.UUCP (Dave Kraft) writes:
>Hi,
>I'm looking for a sort algorithm that is portable
>between Turbo C 2.0 and Xenix.  Or, if someone ...

Here's one that is portable between many ANSI-fied dialects.  You will have
to un-ANSI-fy the declarations if you want to use it on an older version of
C, and of course <string.h> may be <strings.h>, etc., that type of thing.

It's not a quicksort; it's a Shell sort, which is slower in the long run but
is faster for 1) small amounts of data or 2) well-ordered data.  You probably
won't notice much difference (unless your library's qsort was hand-coded in
assembly language).  People may argue over my choice of h (I use 2^n - 1),
but I won't consider my code defiled regardless of what you do to it.

On my VAXstation it sorts 10,000 integers in 22 seconds.  qsort takes about
6 seconds.  (alas!)  ssort and qsort both take <1 second to sort 1,000
integers.

See Knuth (v.3, p.85) for more details.  The Shell sort is the most
compact of the effective sorting algorithms, and is interesting (I think)
to look at.  Everybody has seen heapsorts and quicksorts, anyway ...
This is a pointerized version that isn't so pretty to the eye, but has
a minimum of multiplications and complex address calculations.

This code is mine, and I (drum roll please) hereby release it into the
public domain.

---cut here---
#include <stdlib.h>
#include <string.h>

typedef int (*compar_t)(const void *, const void *);

void ssort(void *base, size_t nmemb, size_t size, compar_t compar)

{
	char *K, *Ki, *Kj, *last;
	size_t h, hSize;

	K = (char *) malloc(size);
	last = (char *) base + size * nmemb;

	for (h = (nmemb >> 1) - 1; h > 0; h = ((h + 1) >> 1) - 1) {
		hSize = size * h;
		for (Kj = (char *) base + hSize; Kj < last; Kj += size) {
			for (
				memcpy(K, Kj, size), Ki = Kj - hSize;
				((*compar)(K, Ki) < 0) && (Ki >= (char *) base);
				Ki -= hSize
			) {
				memcpy(Ki + hSize, Ki, size);
			}
			memcpy(Ki + hSize, K, size);
		}
	}

	free(K);

}



v   v sssss|| joseph hall                      || 4116 Brewster Drive
 v v s   s || jnh@ecemwl.ncsu.edu (Internet)   || Raleigh, NC  27606
  v   sss  || SP Software/CAD Tool Developer, Mac Hacker and Keyboardist
-----------|| Disclaimer: NCSU may not share my views, but is welcome to.