From: stirling@ozrout.uucp (Stirling Westrup)
Subject: Name this sort routine.
Organization: Andre P. Ozrout
Date: Wed, 09 Sep 1992 11:34:19 GMT
Summary: What is the name of this sort technique?


I was recently working on a piece of code in which I was handed a linked
list of objects, that was created in no particular order.  I had to process
the individual links in ascending order, based on a key stored in the
links.  I invented the following algorithm to apply a function to each link
in the list, in order.  Now that I've tested it and it works, I've been 
wondering what I should call it.  I assume (with a 86.7% probability) that
it is a modification on one of the standard sort algorithms, but I'm darned
if I recognize it.  I'm including a test program to illustrate how the
algorithm works.

One final point, the following code does not seem to be too terribly fast,
but the lists it will be handling are on the order of only about 50 entries
anyway, so its no big deal.

(Hey, if it really is a new algorithm, I get to name it, right?  How
about 'Stirling's Sort'?  Has a nice ring to it, doesn't it?)

-------------------------------8<---CUT HERE------>8----------------
/* Does this sorting algorithm have a name? */

#include <stdio.h>
#include <stdlib.h>
#include <values.h>

#define NUM 100
#define INT_MIN (MAXINT+1)      /* I wonder how portable this line is ... */
#define INT_MAX (MAXINT)

#define new(T) malloc(sizeof(T))
#define old(v) free(v)

typedef unsigned int Nat;
typedef struct Lst Lst;

struct Lst
  { int key;
    Lst *prv;
    Lst *nxt;
  };


/*
  Add a new link to the front of the list
*/
Lst* lst_add
  ( Lst *lst,
    int key
  )
  { Lst *tmp = new(Lst);

    if( tmp )
      {
	tmp->key = key;
	tmp->prv = NULL;
	tmp->nxt = lst;
	if( lst )
	  lst->prv = tmp;
      }
    return tmp;
  }

/*
  Remove the indicated link from the List
*/
Lst *lst_rmv
  ( Lst *lst,
    Lst *lnk
  )
  { Lst *ret;

    if( lnk->prv )
      {
	lnk->prv->nxt = lnk->nxt;
	ret = lst;
      }
    else
      ret = lnk->nxt;
    if( lnk->nxt )
      lnk->nxt->prv = lnk->prv;
    old(lnk);
    return ret;
  }



/*
  Apply the function <func> to the links of the list, in order by the
  value of the link keys.
*/
void lst_do_sorted
  ( Lst *lst,
    int kmin,
    int kmax,
    void (*func)
      ( Lst *lnk,
	void *arg
      ),
    void *arg
  )
  { int key;

    if( lst == NULL )
      return;
    key = lst->key;

    /*
      if the key is not in the current interval, ignore it, but process
      the rest of the list in the same interval
    */
    if( key < kmin || key > kmax )
      {
	lst_do_sorted(lst->nxt, kmin, kmax, func, arg );
	return;
      }

    /*
      first apply the function to all of the lesser keys that exist
      in the list
    */
    if( key > kmin )
      lst_do_sorted(lst->nxt, kmin, key-1, func, arg );

    /*
      Then apply the function to this link
    */
    func(lst,arg);

    /*
      Finally apply the function to all other keys which are greater
      or equal to this one.
    */
    lst_do_sorted(lst->nxt, key, kmax, func, arg );

    return;
  }


/*
  The function to apply.  In this case, we merely print out the key.
*/
void display
  ( Lst *lnk,
    void *arg
  )
  {
    printf("%6d  ",lnk->key);
  }


int main
  ( int argc,
    char *argv[]
  )
  { Nat i;
    Lst *lst = NULL;
    Lst *tmp;

    srand(999);
    for( i = 0 ; i < NUM; i++ )
      lst = lst_add(lst,rand());
    printf("Unsorted List:\n");
    for( tmp = lst; tmp; tmp = tmp->nxt )
      /* don't you wish x ->= y worked? */
      printf("%6d  ",tmp->key);
    printf("\nDisplayed in sorted order:\n");
    lst_do_sorted(lst, INT_MIN, INT_MAX, display, NULL );
    printf("\n");
    for( i = 0 ; i < NUM; i++ )
      lst = lst_rmv(lst,lst);
    return 0;
  }
-- 
||    BUNGEE SIDEWAYS!                              o   )))
||                                                 /-- ///
|P~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\_  \\\      __ -_
||    stirling@ozrout.uucp                                 ((( (_)T(_)