Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/altsrcs/1/1685

Internet Message Format | 1990-12-28 | 20.5 KB

From: [e-mail] (Wayne Diener)
Newsgroups: alt.sources
Subject: Sorting Algorithm
Message-ID: <[e-mail]>
Date: 16 Aug 90 23:00:00 GMT

I have been unable to find any references to the sorting algorithm
used in this program.  If anyone has seen it elsewhere, I would
appreciate hearing about it.  None of my "guru" programmer friends,
my professors (I'm a hardware type who went back to college to learn
a little software) or a literature search have turned up an equivalent
so I'm posting it here to see if any one already knows of it.  If it's
original with me, I claim a copywrite on it and release it for use
by anyone.  I'm certain it can be improved - feel free to do so, but
send me a hard copy via US mail, OK?

I have done empirical comparisons of this sort against bubble,
insertion, selection and queuemerge sort.  It's a lot faster than
the first three but slower than the queuemerge sort, however, it
does the sort "in-place" (requires very little additional memory,
other than a few more variables).  I'm not really terribly proficient
at "Big O" analysis, but it LOOKS like it might be O(N*log(N))
instead of O(N^2).  Anyone want to analyse it?

I 'trimmed' this file from the original form (massive documentation
for class requirements) to include only what I think is really
useful.  I don't think I cut out anything important, but I can't
be 100% sure since I haven't re-compiled.  The sorting algorithm itself
should be okay.  I compiled and ran the program using Turbo C,
cc on a Sun 386i and under Ultrix, so it should work in most environments.

The sorting is accomplished using a binary search of a linked list
to find the the proper insertion point (just running up and down
the pointers and dividing the list in half each time) and then
moving the pointers to change an item's location.

Have fun, and not too many flames, OK? (Remember this was a class
assignment (for string manipulation actually) and I had to demonstrate
some concepts other than just the sorting.)


X-----------------------  CUT  ----------------------------------------X
/***********************************************************************
   A "Binary Insertion Sorting Technique for Linked-Lists"
   Wayne D. Diener
   South 3415 Myrtle
   Spokane, WA  99223
   [phone]

    This program reads a file of input words (as you might type
    them in with any programming editor), prints the word count
    and the list of words, sorts the list and then prints the
    list again.

    (Oh, yea...  Bi_In_Sort() is the actual function)


   *inp         FILE          Used to read the characters from the input
                              file.
   ch           char          Used for input to "hold" the screen long
                              enough to see the results.
   *mnlst       main_list    A pointer to the header for the list.

************************************************************************/

#include <stdio.h>
#include <fcntl.h>
typedef char data;

typedef struct node              /* Each node contains a character. */
{
   data character;
   struct node *next_letter;
   struct node *prev_letter;
} node;

typedef struct header            /* Each header starts a word. */
{
   int letter_count;
   struct node *word_head;
   struct node *word_tail;
   struct header *next_word;
   struct header *prev_word;
} header;

typedef struct main_list         /* This is the main list header. */
{
   int word_count;
   struct header *head_word;
   struct header *tail_word;
} main_list;


main(argc,argv)

   int argc;
   char *argv[];

{
   FILE       *inp,*fopen();
   int        ch;
   main_list  *mnlst;
   void       read_list();
   void       print_list();
   void       erase_list();
   void       Bi_In_Sort();
   int        compare_words();

   if (argc != 2)
   {
      printf("Error.  Useage:  %s filename",argv[0]);
      exit(1);
   }

   if ((inp = fopen(argv[1],"r")) == NULL)
   {
      printf("Could not open %s for input.",argv[1]);
      exit(1);
   }
   mnlst = (main_list *) malloc (sizeof(main_list));

   read_list(mnlst,inp);  /* Read the words into a list. */

   fclose(inp);     /* Close the input file. */

   printf(" Word count = %d\n",mnlst->word_count);

   printf("\n The input word list printed forward is:\n\n");
   print_list(mnlst->tail_word,0);  /*It's recursive so start at wrong end*/

   Bi_In_Sort(mnlst,compare_words);              /* Sort the list. */

   printf("\n The sorted word list is:\n\n");
   print_list(mnlst->tail_word,0);
   printf("\n\n\n Press return to continue.\n");
   scanf("%c",&ch);      /* Leave the screen up until a <cr> */
   erase_list(mnlst);    /* Clean up the memory. */

}

void
print_word(ptr)
   header *ptr;
/***********************************************************************
   print_word() - accepts a pointer to the header of a word it prints
   out all the characters contained in the list at that node and then
   prints a space character.

   variables used:
   name         type                     Description
   -------------------------------------------------------------------
   *p           node           Points at the characters to print.
   i            int            A loop control variable that counts letters.
***********************************************************************/
{
   node *p = ptr->word_head;
   int i = ptr->letter_count;
   while (i-- != 0)
   {

      printf("%c",p->character);
      p = p->prev_letter;
   }
   printf("%c",' ');     /* Put a space after it. */
}

void
print_list(point,dir)
   header *point;
   int   dir;
/***********************************************************************
   print_list() - accepts a pointer to one of the word nodes on the list
   and a variable that determines which direction to print (forward or
   reverse).  It then traverses the list of words recursively and prints
   the word contained at each node.

   variables used:
   name         type                     Description
   -------------------------------------------------------------------
   none
***********************************************************************/
                         /* If dir = 0 we'll print the list normally. */
                         /* If dir != 0 we'll print backward. */
{                        /* It works either direction. */
   void Print_word();

   if((dir ? point->prev_word : point->next_word) != NULL)
      print_list((dir ? point->prev_word : point->next_word),dir);
   print_word(point);
}

void
erase_list(list)
   main_list *list;
/***********************************************************************
   erase_list() -  accepts a pointer to the main word list.  It traverses
   the list erase each word list associated with the node, goes to the
   next node and erases the previous header.  Finally it erase the last
   word node and then the header for the main list.

   variables used:
   name         type                     Description
   -------------------------------------------------------------------
   *p            header     Points at the word node to be erased.
***********************************************************************/
{
   header  *p = list->head_word;
   void erase_word();
   while ( p != NULL)  /* p is not passed list->tail_word*/
   {
      erase_word(p);        /* Erase the word. */
      p = p->prev_word;     /* Go to the next word. */
      if (p != NULL)
         free(p->next_word);   /* Free the previous word header. */
   }
   free(list->tail_word);  /* Free the last word header. */
   free(list);             /* Free the list header. */
}

void
erase_word(word_node)
   header *word_node;       /* word_node is the header for the word. */
/***********************************************************************
   erase_word() -  Accepts a pointer to a word node.  It traverses the
   list of character nodes and frees the memory associated with each
   character.

   variables used:
   name         type                     Description
   -------------------------------------------------------------------
   *p           header        A helper pointer.
   *q           header        The pointer used to free the memory.
   i            int           A loop counter used to count the letters.
***********************************************************************/
{
   node *p,*q = word_node->word_head;       /* p points at the letters. */
   int i;
   for (i=0;i < word_node->letter_count;i++)
   {
       p = q->prev_letter;   /* Save the next letter pointer. */
       free(q);              /* Free the letter. */
       q = p;                /* Point at the next letter. */
   }
}

int
compare_words(first,second)
   header   *first,*second;
/***********************************************************************
   compare_words() -  Accepts two pointer to word headers.  It compares
   the letters contained at each node of the word in succession.  If it
   encounters a letter in one word that is greater than the corrsponding
   letter in the other word, it returns the appropriate value.  If the end
   of either (or both) word(s) is reached a determination of the longer
   of the two words is attempted by comparing the lengths of the words.
   If the lengths are different, the function returns the appropriate
   value, if the word lengths are the same, it returns the "equal value".

   variables used:
   name         type                     Description
   -------------------------------------------------------------------
   *p           header        Points to the header of the first word
                              to compare.
   *q           header        Points to the header of the second word
                              to compare.

***********************************************************************/
/*  if first > second, return 0.  If second > first, return 2
if first = second, return 1 */

{
   node *p = first->word_head,*q = second->word_head;

   while ((p != NULL) && (q != NULL))  /* As long as letters are there. */
   {
      if ( p->character > q->character)        /* First > Second. */
         return(0);
      else if ( p->character < q->character)   /* Second > First. */
         return(2);
      else                                     /* Equal so far! */
      {
         p = p->prev_letter;     /* Go to the next letters. */
         q = q->prev_letter;
      }
   }
 /* To get here, one or both of the words is out of letters and they
 are equal to this point. */

   if (first->letter_count > second->letter_count)       /* First > */
      return(0);
   else if (first->letter_count < second->letter_count)  /* Second > */
      return(2);
   else return(1);          /* The words are equal. */
}

void
Bi_In_Sort(big_list,compare)
   main_list *big_list;
   int    (*compare)();

/***********************************************************************
   Bi_In_Sort() - Accepts a pointer to the header of a list to process.
   First, a sorted portion is created at the end of the list that is 2
   items long then a loop is entered that repeatedly takes the next item
   at the "head" of the list and uses a binary search of the items in the
   sorted portion to determine the correct location for the new item.
   The new item is then removed from the head of the list and inserted
   at the appropriate location.  This process is repeated until the last
   item has been processed.

   variables used:
   name         type                     Description
   -------------------------------------------------------------------
   test         int           Used as a flag to signal the instance
                              where the new item should be inserted
                              prior to the present smallest member of
                              the list.
   count        int           Used to keep track of the number of words
                              already in the sorted portion of the list.
   middle       int           Used as a counter control variable to
                              determine how far "up" or "down" the list
                              to travel during the binary search.
   i            int           The count control variable for list traversal.
   up           int           Used as a boolean control variable to determine
                              if the next movement on the list should be
                              "up" the list or "down" the list.
   *current     header        The pointer that is moved "up" and "down" the
                              list while searching for the proper insertion
                              location.
   *newitem     header        A pointer that is used as a "handle" during
                              the movement/insertion of the head of the list.
   *sortbound   header        A pointer that points to the "lowest" item of
                              the sorted portion of the list.

***********************************************************************/
{
   int      test,count=1,middle,i,up;
   header   *current,*newitem,*sortbound;
   void     insert();

   if (big_list->word_count > 1)  /* A one item list is already sorted. */
   {
      current = big_list->tail_word->next_word;
      if ( (*compare)(current,big_list->tail_word) == 0)
      {
         current->next_word->prev_word = big_list->tail_word;
         big_list->tail_word->next_word = current->next_word;
         current->next_word = big_list->tail_word;
         big_list->tail_word->prev_word = current;
         current->prev_word = NULL;
         big_list->tail_word = current;
      }
      /*   The sorted part is now two items long. */
      sortbound = big_list->tail_word->next_word;
      do
      {
         up = 1;                         /*"Outside loop" initializations.*/
         newitem = big_list->head_word;
         count++;
         middle = (count +1) / 2;
         current = sortbound;
         test = 0;
         do
         {
            for ( i=0; i < middle ; i++)
            /* Go to the appropriate "middle". */
            {                          /* Either up or down the list. */
               current = up ?   current->prev_word : current->next_word;
               if (current == sortbound)
               {
                  test = 1;          /* If we get to the sort boundary, */
                  break;             /* we have to quit. */
               }
            }
            if (((*compare)(newitem,current) == 0) && current != NULL)
            {
               if (current == big_list->tail_word)
               /* Place the item at the tail. */
               {
                  big_list->head_word = newitem->prev_word;
                  big_list->head_word->next_word = NULL; /* the new head */
                  newitem->prev_word = NULL; /* the new end of the list */
                  newitem->next_word = big_list->tail_word;
                  big_list->tail_word->prev_word = newitem;
                  big_list->tail_word = newitem;
                  break;
                  /* The sortbound stays in the same place. */
               }
               else
                  up = 1;     /* Otherwise we have to look further "up". */
            }
            /*  The case of inserting after the tail_word is finished. */
            else if(test)   /* To get here, newitem <= current */
                            /* and current = sortbound */
                            /* so we insert before current */
                            /* and move sortbound to the new item. */
            {
               if ( current == newitem->prev_word)
                  return;   /* This is the actual finishing point. */
               else
               {
                  insert(big_list,newitem,current);
                  sortbound = newitem;
                  break;
               }
            }
            /*  Inserting before sortbound is finished. */
            /*  To get here, newitem <= current and somewhere in the middle*/
            else if ( (*compare)(newitem,current->next_word) <= 1)
            {
               insert(big_list,newitem,current);
               break;
            }
            else
            /*  newitem is strictly less than current->next, so: */
            /*  go down the list.  */
               up = 0;
       middle /=2;
       if (middle == 0)
          middle++;
       }
       while (1);
    }
    while (sortbound != big_list->head_word);
    }
}

void
read_list(ml,inp)
   main_list *ml;
   FILE     *inp;
{
   node       *dat;
   header     *list;
   char       a, ch = 32;    /* This makes the initial while loop work. */
   void       print_word();

   while ((ch == 32) || (ch == 13) || (ch == 10))
      ch = getc(inp);  /* This halts formation of words from */
   ungetc(ch,inp);   /* leading spaces, etc. (no letters). */

   if((ch = getc(inp)) != EOF)
   {
      dat = (node *) malloc (sizeof(node));
      list = (header *) malloc (sizeof(header));
      ml->head_word = list;      /* Points to the head of the whole list. */
      ml->tail_word = list;      /* Points to the tail of the whole list. */
      ml->word_count = 1;        /* There's at least one word in the list. */

      list->letter_count = 1;    /* There's at least one letter in the word. */
      list->word_head = dat;     /* This points at the first letter. */
      list->word_tail = dat;     /* This points at the last letter. */
      list->next_word = NULL;    /* This is the only word so far. */
      list->prev_word = NULL;


      dat->character = ch;  /* This is the first letter of the first word. */
      dat->next_letter = NULL;     /* It's also the only letter right now. */
      dat->prev_letter = NULL;

      while(ch != EOF)
      {
         if((ch=getc(inp)) != EOF)
         {
            if((ch == 32) || (ch == 13) || (ch == 10))
            {                   /* New word.  Make a new word header node. */
                                /* The following while, ungetc and if(ch..) were also necessary
                                        if allowing <cr> and <lf> as word seperators. */
               while ((ch == 32) || (ch == 13) || (ch == 10))
                                                ch = getc(inp);  /* This halts formation of words from */
               ungetc(ch,inp);   /* extra spaces, etc. (no letters). */
                                 /* but put the last character back. */
               if (ch == EOF)    /* This protects agains a final word */
                                                break;         /* being generated at EOF. */
               list = (header *) malloc (sizeof(header));
               /* link it into the main_list. */
               list->prev_word = NULL;               /* It's the new end. */
               ml->tail_word->prev_word = list;
               list->next_word = ml->tail_word;
               ml->tail_word = list;    /* Adjust the end of the word list. */
               ml->word_count++;        /* Increment the word count. */
               list->letter_count = 0;  /* No letters in the word yet. */
            }
            else if((ch != 10) && (ch != 13))
            /* Disallow <cr> and <lf> as actual parts of the words. */
            {
               dat = (node *) malloc (sizeof(node));
               dat->prev_letter = NULL; /* This is the new end of the word*/
               dat->character = ch;     /* Place the letter in the node. */
               if (list->letter_count == 0)  /* No letters in the word yet*/
               {
                  list->word_head = dat;   /* Point at the end of the word*/
                  dat->next_letter = NULL; /* The first letter has no next*/
               }
               else
               {
                  list->word_tail->prev_letter = dat; /* Link to end word */
                  dat->next_letter = list->word_tail;
               }
               list->letter_count++;  /* Increment the letter count. */
               list->word_tail = dat; /* The new end of the word. */
               }
         }
      }
   }
}

void
insert(bg_lst,new,cur)      /* These are the common statements required*/
   main_list *bg_lst;       /* for any insertion prior to current pointer*/
   header    *new,*cur;
/***********************************************************************
   insert() - Accepts the pointers to the main list and the current
    and newitem and performs an isertion of the new item prior to the
    current location.

   variables used:
   name         type                     Description
   -------------------------------------------------------------------
   none
***********************************************************************/
{

   bg_lst->head_word = new->prev_word;
   bg_lst->head_word->next_word = NULL;
   new->next_word = cur->next_word;
   cur->next_word->prev_word = new;
   cur->next_word = new;
   new->prev_word = cur;
}