|
QuickSort is nice, but it's usually implemented using statically allocated arrays, and it does not take advantage of already-sorted data. Bill's variation of the Merge Sort addresses both of these weaknesses.
June 01, 1999
URL:http://www.drdobbs.com/database/efficiently-sorting-linked-lists/184410973
Bill is a professor of computing science at the University of Central Oklahoma. He can be reached at mcdaniel@aix1 .ucok.edu.
I've become a big fan of the merge sort recently, ever since someone pointed out that it never degenerates into an O(N2) algorithm as quicksort does. This month, Bill McDaniel shows how to speed up the merge sort even more by keeping already-sorted sections together.
As a bonus, Bill's algorithm is also a good place to demonstrate Igor Kolpakov's technique for simplifying linked-list operations. Igor recently wrote me to explain the technique, which I describe in the accompanying text box "Simplifying Linked Lists."
If you have a favorite trick you'd like to share with other DDJ readers, write me at [email protected].
-- Tim Kientzle
Many sorting algorithms require you to go through a fixed set of operations, even if the input data is already mostly sorted. I wanted to develop an algorithm for sorting, using linked lists, that capitalizes on already ordered subsequences. In particular, a list that's nearly ordered should sort very quickly.
I also wanted a routine that would work well even when the data was in the worst possible order. Quicksort has been used for years, and has been considered to be the best overall sort for randomly distributed data. However, quicksort is slow -- approaching O(N2) -- when the data is ordered (either forward or backward). In addition, the algorithm is defined and implemented recursively, which results in more overhead and, hence, slower run times.
My starting point for the development of this algorithm was the merge sort, described in many algorithm books. My algorithm is similar to Donald Knuth's "list merge sort," except that Knuth uses an extra bit to mark the ends of sublists, whereas I look for patterns in the data itself to identify sublists.
Many lists to be sorted already have sections that are in the correct order. Suppose you took a list with R sorted sections and split it into separate sorted lists, as in Figure 1.
The basic idea behind my algorithm is to merge successive pairs of lists. Each such merge requires O(N) time, since it requires examining every item. Each merge pass halves the number of lists so you make a total of log2(R) passes. Note that R, the number of sorted sublists, is always less than N, so the total time is never more than O(N log N). And, if the original list was mostly sorted, R will be very small and the algorithm will complete quickly.
Instead of having R lists, my algorithm (which I refer to as the "McDaniel Sort") uses just two output lists. As Figure 2 shows, the first one holds the even sections, the second holds the odd sections.
With this arrangement, I only need four lists -- two input lists (Figure 2) and two output lists (Figure 3). During each pass, I merge sections from the input lists and alternate the resulting sorted sections in the output lists. Figure 3 shows how I merge L0 and L1 to make L01, merge L2 and L3 to make L23, and so on.
The tricky part is knowing where one group (L0 and L1) ends and the next group (L2 and L3) begins. This can be determined by comparing the first elements in both input lists to the last element sent (to either output list). If the first elements in both input lists are less than the item just output, this indicates the start of a new group.
The loop at the bottom of Example 1 is the essential part of my algorithm. In each iteration of this loop, you can choose the first element from either input list and place that element at the end of either output list. Remember that you want to construct long sorted sequences. If only one of the candidates is larger than the last item output, then that's the only one that can continue the current sorted sequence. If both candidates are larger, then choosing the smaller of the two will let you construct a longer sequence. If both candidates are smaller, then you have to start a new sequence, so choosing the smaller will let that new sequence be as long as possible.
Of course, since you want to alternate sorted sequences between the two output lists, whenever you start a new sequence, you switch output lists.
Listing One presents the complete algorithm. The central loop involves comparing new candidate elements to the last element output. This requires that you initialize the first output list with the first element from one of the input lists. The second output list is initially set to empty.
The outermost do/while loop retrieves items from the two input lists and sends them to the output lists. The code inside this loop constitutes one pass. When the loop is finished, the second output list is checked. If the second output list (out[1]) is empty, then all of the items were routed to the first output list and the items are all sorted. If the second output list is not empty, then another pass is required.
The code to select an item from the correct input list is fairly complex because you have to determine the relative order of the last item output and the first item in each input list. Whenever you select an input item smaller than the last output item, you have to switch output lists.
The algorithm is surprisingly fast. The best case behavior occurs with a list whose items are already sorted. The sort will be finished after one pass. The worst case is when the items are in reverse order. For a list of N items, it will take log2(N) complete passes to sort the items, making the order of this algorithm Nlog2(N).
I've implemented the code in C for clarity. This code illustrates several programming ideas, one of which involves passing the address of the comparison routine as a parameter. This lets the code sort a linked list of virtually any structure, as long as the first field of the structure is a pointer to the next item.
To use the Sort function, you must first write a compare routine (comp) that references any user-defined fields of the structure. This function contains a "less_than" test, that returns True (1) if the item pointed to by the first parameter is less than the item pointed to by the second parameter; otherwise, it returns False (0). The parameters to comp are void pointers simply because comp is not yet written. The function LT_comp in Listing Two is a good example. Listing Two is a sample program that sorts a text file.
This sort works well for random data, data that has sorted subsequences, and data that has a lot of duplicate keys. It can be used in a variety of different situations, and -- unlike quicksort -- does not involve recursion.
DDJ
typedef struct GenericNode GenericNode;
struct GenericNode { GenericNode *next; };
void Sort(void ** pList, int (*comp) (void *, void *))
{
int outindex; /* current output list (0 or 1) */
GenericNode *p; /* Scratch variable */
GenericNode *in[2], *out[2]; /* Input/Output lists */
GenericNode **outTail[2]; /* Track last items in output lists */
GenericNode *lastOut; /* Last node output */
if(!*pList) return; /* Empty list is already sorted */
out[0] = *pList; /* point out[0] to the list to be sorted */
out[1] = 0;
do {
in[0] = out[0]; /* Move output lists to input lists */
in[1] = out[1];
if (!in[1]) { /* Only one list? Grab first item from other list */
p = in[0]; if(p) in[0] = in[0]->next;
} else { /* There are two lists, get the smaller item */
int smallList = comp(in[0],in[1]) ? 0 : 1;
p = in[smallList]; if(p) in[smallList] = in[smallList]->next;
}
/* Initialize out[0] to first item, clear out[1] */
out[0] = p; outTail[0] = &(p->next); lastOut=out[0];
p->next = (GenericNode *)0;
outindex = 0;
out[1] = (GenericNode *)0; outTail[1] = &(out[1]);
while (in[0] || in[1]) { /* while either list is not empty */
if (!in[1]) { /* Second list empty, choose first */
p = in[0]; if(p) in[0] = in[0]->next;
if(comp(p,lastOut)) /* p < lastOut */
outindex = 1-outindex; /* switch lists */
} else if (!in[0]) { /* First list empty, choose second */
p = in[1]; in[1] = in[1]->next;
if(comp(p,lastOut)) /* p < lastOut */
outindex = 1-outindex; /* switch lists */
} else if (comp(in[0],lastOut)) { /* in[0] < lastOut */
if(!comp(in[1],lastOut)) { /* lastOut <= in[1] */
p = in[1]; in[1] = in[1]->next;
} else { /* in[1] < lastOut */
if(comp(in[0],in[1])) { /* in[0] < in[1] */
p = in[0]; in[0] = in[0]->next;
} else {
p = in[1]; in[1] = in[1]->next;
}
outindex = 1-outindex; /* Switch lists */
}
} else { /* lastOut <= in[0] */
if(comp(in[1],lastOut)) { /* in[1] < lastOut */
p = in[0]; in[0] = in[0]->next;
} else { /* lastOut <= in[1] */
if(comp(in[0],in[1])) { /* in[0] < in[1] */
p = in[0]; in[0] = in[0]->next;
} else {
p = in[1]; in[1] = in[1]->next;
}
}
}
*outTail[outindex] = p;
outTail[outindex] = &(p->next);
p->next = (GenericNode *)0;
lastOut = p;
}
} while (out[1]);
*pList = out[0];
}
/* llsort.c. Sort 1 or more lines of text.
* Usage: llsort <infile> <outfile> <optional sort column>
* Sort column - defaults to 1.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxLength 1000 /* n is the maximum length of an input line */
/* If you're sorting on the first column, sortPointer will point to first
* character of 'info'. Otherwise, it will point further into the string. */
typedef struct MyNode {
struct MyNode *next;
char *sortPointer; /* Pointer to string to be sorted */
char info[1]; /* String data */
} MyNode;
int LT_comp(void *a, void *b) {
char *p=((MyNode*)a)->sortPointer;
char *q=((MyNode*)b)->sortPointer;
return (strcmp(p,q) < 0); /* True if a<b */
}
int main (int argc,char **argv)
{
FILE *infile, *outfile;
MyNode *p, *list, **pTail;
long int sort_column = 0;
char st[maxLength], infn[256], outfn[256];
if (argc < 2) {
printf("Usage: %s infile outfile [number] \n",argv[0]);
exit(1);
}
/* pick off the file names */
strcpy( infn, argv[1]);
strcpy(outfn, argv[2]);
/* pick off the starting sort column (if it exists) */
sort_column = 0;
if (argc == 4 ) sort_column = atol(argv[3])-1;
/* open the files */
infile = fopen(infn,"r");
if (!infile) {
printf("File %s could not be found.\n",infn);
exit(1);
}
outfile = fopen(outfn,"w");
if (!outfile) {
printf("Output file %s could not be opened.\n",outfn);
exit(1);
}
/* initialize the list */
list = 0; pTail = &list;
/* read the input file and build the linked list */
while (fgets(st,maxLength,infile)) /* get one line */
{
/* fetch a node that is just the right size */
p = malloc(sizeof(MyNode)+strlen(st)+1);
if(!p) {
fprintf(stderr,"Out of memory!");
return 1;
}
/* copy the string into the info portion of the node */
strcpy(p->info,st);
/* sortPointer points to the part of the string being sorted */
if (strlen(p->info) < sort_column) {
p->sortPointer = ""; /* Too short, treat as empty string */
} else {
p->sortPointer = p->info + sort_column;
}
/* insert the node onto the tail end of the list */
*pTail = p; pTail = &(p->next);
}
*pTail = 0; /* Terminate list with null */
fclose(infile);
printf("Sorting: %s by column %ld\n",infn, sort_column+1);
Sort((void**)&list, LT_comp);
/* Send the sorted data to the output file. */
p = list;
while(p) {
fputs(p->info,outfile);
p = p->next;
}
fclose(outfile);
return 0;
}
/* Igor Kolpakov's "reverse pointer" trick */
typedef struct _ITEM ITEM;
struct _ITEM {
int key;
ITEM * next;
};
ITEM *listHead;
AddItem(ITEM *newItem) {
/* Keep a 'reverse pointer' to the pointer to this item */
ITEM ** rpItem = &listHead;
ITEM * item = listHead;
while(item && (key > item->key)) {
rpItem = &item->next;
item = item->next;
}
/* Note: No extra tests!! */
*rpItem = newItem;
newItem->next = item;
}
DeleteItem(int key) {
ITEM ** rpItem = &listHead;
ITEM * item = listHead;
while(item && (key > item->key)) {
rpItem = &item->next;
item = item->next;
}
if(item && (key == item->key)) {
/* Note: No extra tests!! */
*rpItem = item->next;
free( item );
}
}
Move the two output list pointers to the two input list pointers.
Set the two output list pointers to NULL.
Move the first item from the first input list over to the first output list.
Loop while there are items in either of the two input lists
{
Select a node to remove from the appropriate input list.
Determine which output list to send the node to.
Move the node selected into the appropriate output list.
}
(a)
L0[1] ... L0[n0], L1[1] ... L1[n1], ..., L(R-1)[1] ... L(R-1)[n(R-1)]
(b)
0 1 2 . . . . . . . R-1
- - - ---
L0[1] L1[1] L2[1] L(R-1)[1]
L0[2] L1[2] L2[2] L(R-1)[2]
L0[3] L1[3] L2[3] L(R-1)[3]
. . .
. . .
. . .
L0[n0] . L(R-1)[n(R-1)]
L1[n1] .
.
L2[n2]
list 0: L0[1] ... L0[n0], L2[1] ... L2[n2], ... list 1: L1[1] ... L1[n1], L3[1] ... L3[n3], ...Figure 2: Splitting a list by alternating sorted sections.
Output list 0: L01[1] ... L01[n0+n1], L45[1] ... L45[n4+n5], ... Output list 1: L23[1] ... L23[n2+n3], L67[1] ... L67[n6+n7], ...
Normally, you need just one pointer to traverse a linked list. But, if you need to modify the list, the textbooks tell you to keep a second pointer that tracks the previous item. This second pointer allows you to update the "next" field of the previous item. However, this complicates inserting or deleting the first item, since you then must update the list head rather than the next field of some item.
Igor Kolpakov pointed out to me that it's much simpler if the second pointer just tracks the pointer that needs to be updated, rather than the entire previous item. This works whether you need to update the list head or a "next" field.
Listing Three shows how this one slight change removes a lot of conditional logic from the textbook list management code.
DDJ
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.