Sorting Algorithm
Wayne Diener
wayned at wddami.spoami.com
Fri Aug 17 09:00:00 AEST 1990
[ I posted this to alt.sources and received a suggestion that
I repost to comp.lang.c. If you have trouble mailing to me
you might try:
To: isc-br!hawk!wddami!wayned at uunet.uu.net
]
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
(509) 535-4670
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;
}
More information about the Comp.lang.c
mailing list