Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Database

Algorithm Alley


Algorithm Alley

John is a software-development manager at UWI.Com -- The Internet Forms Company. John is also a part-time theoretical computer-science graduate student at the University of Victoria. He can be contacted at [email protected].


Generic collection classes, such as those in the C++ Standard Template Library and Java Developer's Kit, are nice to have around, in part because they encapsulate standard algorithms that are useful in many situations. But such libraries are hard to write -- how do you know, for instance, that the particular algorithm you chose will work well across so many applications? As you'll see upon reading John's article, even experts such as those writing the JDK can sometimes overlook the best algorithm choices.

I found John's discussion of linked list searching especially interesting. Like many people, I failed to distinguish between the cost of walking a link and the cost of a key comparison. Understanding that distinction makes a big difference.

-- Tim Kientzle

Some common misconceptions in computing are that arrays can be sorted more quickly than linked lists; that the quicksort is the fastest comparison sort on average; and that binary searching a linked list provides no benefit over a sequential search because both are O(n).

If you agree with any of the aforementioned views, you're in good company. The list sort and search algorithms in the recently released Java Developer's Kit (JDK) 1.2 beta 2 are based on these misconceptions, which results in suboptimal performance.

In this article, I'll present Java implementations (available electronically, see "Resource Center," page 3) of more-efficient list sort and search algorithms, which are based, in part, on my undergraduate thesis work in 1988. These algorithms also have the advantage that they work on both singly and doubly linked lists (although the sorts require a simple post-processing loop for doubly linked lists to reconnect all of the references to previous nodes).

Performance

Although I collected empirical results on a 64-MB 200-MHz Pentium running Windows 95, I also ran the tests on other machines. While the numbers change, the conclusions are the same.

The test program allows you to specify the number of randomly generated ten-character strings to sort or search. As you type your number, the program will not show you what you are typing. This is a bug in Java's Kbd.readLine() function. However, if you simply type your number on faith and press Enter, your input will be properly recognized. You can then choose a sort or search test. The sort test runs five different sort functions: the array quicksort in Arrays.sort(), the linked-list quicksort in Collections.sort(), a new linked-list quicksort, a new linked-list merge sort, and a nonrecursive version of the linked-list merge sort. The search test compares the new binary search to the sequential search in Collections.binarySearch(). The search tests simply use the search to find every string in the array or list.

Figure 1 shows the results of the sort tests on 16,000 strings. The limitations of System.currentTimeMillis() (which is only updated every 50 to 60 milliseconds on Windows 95) make it difficult to distinguish the two list merge sorts. With 32,000 strings, the Java VM froze without any errors, so I was unable to empirically test which of my two new list sorts was faster.

All of the new linked-list functions sort linked lists faster than Arrays.sort() can sort the equivalent array. Since Collections.sort() calls Arrays.sort(), naturally all of the new linked-list sorts are much faster than the JDK's linked-list sort. This was not just on average but in every test case. The most notable result is that the JDKv1.2b2 Collections.sort() was 33 percent slower than the recursive merge sort, and the Arrays.sort() function was slower than the linked-list merge sort by 22 percent. Best of all, the merge sort cannot degrade to quadratic time for any data set. Thus, it is not true that linked-list sorting must be slower than array sorting, nor is it true that the quicksort is the fastest comparison sort.

As Figure 2 shows, the linked-list binary search was over nine times faster on average than the sequential search using 1000 to 4000 randomly generated strings. The shapes for both searches are parabolic because the searches are O(n), and the test program searches for every string in the list, yielding O(n2) test performance.

Small Errors, Big Impact

When first testing Collections.sort(), I noticed it was getting results that were poorer than I expected -- 140 seconds for 16,000 strings. Collections.sort() only adds a few linear time operations to an O(n log n) array sort, so it shouldn't be much slower than array sorting.

The first step of Collections.sort() is to convert the linked list to an array; this was taking 136 seconds in my first test. The toArray() function itself turned out to be O(n2), apparently because the iterator's next() function in LinkedList restarted at the beginning of the list in each call. As a temporary fix, my test program subclasses LinkedList to overload the iterator() function. The new version merely returns listIterator(), with a substantial performance improvement.

Linked-list Quicksort

It may come as something of a surprise that the quicksort can be done on a singly linked list since it is impossible to efficiently traverse backwards. In fact, I haven't encountered any other work describing a linked-list partition sort, so I believe that this is an original algorithm (though I'd be glad to hear from any reader who knows otherwise). Listing One is Java source for this new sort.

The basic method uses the first node's key as the pivot. The algorithm traverses forward through the list using two references called aNode and aNodePrev. Nodes with a key value greater than or equal to the pivot are ignored. When a node containing a lesser key is encountered, the algorithm deletes aNode by connecting aNodePrev.next to aNode.next. Then, aNode is pushed onto the front of the list, becoming the new first node. Once the list is divided into two sublists, it can be sorted by recursively applying this partitioning procedure to each sublist.

This still leaves the quicksort's problem of quadratic performance on sorted/nearly sorted and reversed/nearly reversed data. The simplest and most popular solution to this problem is the median of three method, which can be effected in constant time per subarray partition. However, the median of three method requires linear time to scan the entire linked list prior to the partition pass. Truthfully, this really isn't such a bad idea. Since the partition already takes linear time, having the median of three method take O(n) time doesn't change the O(n log n) average case rating of the sort. The demo program (available electronically) provides a median of three function for the list quicksort.

But if linear time is acceptable, then it is possible to do something more elegant. In the case of the linked-list quicksort, the pivot advancement method (see Figure 3) is much shorter to code and easier to understand, yet it results in much faster performance on random data as well as O(n), overall sort behavior on nearly sorted and nearly reversed lists.

Pivot advancement starts with two references, Pivot and aNode, at the start of the list. The algorithm advances aNode through the list as long as it is monotonic nondecreasing, and every two advancements of aNode yields one advancement for the Pivot. If the pivot advancement loop traverses the entire sublist, then it is sorted so the function returns with no further processing. If the pivot advancement loop does not traverse the entire loop, then the pivot is the median element of the entire monotonic nondecreasing sublist at the start of the input list. Furthermore, we leave aNode at its given position rather than starting the partition loop at the node after the pivot because the nodes between the Pivot node and aNode are already known not to have lesser key values than the pivot.

Thus, with only one extra comparison per partition, pivot advancement handles nearly sorted data sets in linear time rather than quadratic time. Reversed data is also handled in linear time because nodes pulled from the second sublist are pushed onto the front of the first sublist, which reverses them into sorted order. On random data, pivot advancement outshines median of three because the former does little work in choosing a pivot at or near the beginning of the list (rather than traversing the whole list). The probability that aNode will be advanced in random data sets diminishes exponentially (1 in 2i chances of i advancements).

Finally, note that the linked-list quicksort presented here still has a quadratic worst case. The worst case occurs with sequences with the pattern 3,2,1,6,5,4,9,8,7... However, these worst case examples are unlikely to occur in practice, and the expected running time is O(n log n) with low hidden constants.

Linked-List Merge Sort

Conventional wisdom has it that the quicksort is quicker than all other comparison sorts, and the merge sort in particular. However, this conclusion is generally based on analyzing the merge sort's performance on an array, which is not the ideal data structure for the merge sort. The merge of two sorted arrays requires an auxiliary array, which ultimately results in the merge sort performing twice as many movement operations as the quicksort on average. By comparison, the linked-list merge operation can be done in-place with only constant memory overhead for a few temporary variables. This eliminates both of the detracting factors for the merge sort. In fact, since the merge sort performs fewer key comparisons than the quicksort on average, it is the merge sort that should be quicker when sorting linked lists.

As the empirical results show, the linked-list merge sort (see Listing Two) on a linked list is so fast that it outperforms the quicksort in Arrays.sort() using the same data placed in an array. The list quicksort presented in this article is also slower than the list merge sort by an average 6 percent. Furthermore, the merge sort's recursive calls always divide the list evenly in half. So, given that the merge step is a simple linear time process, the merge sort can never be slower than O(n log n). Finally, the guaranteed logarithmic function call depth means that the merge sort will never generate a stack overflow exception. A worst case array quicksort could generate an exception in Java with as few as 5000 elements, which is the current size limit on Java's function call stack.

Nonrecursive Merge Sort

It is also commonly believed that non-recursive sorts are better than recursive ones. Again, this is due to the quicksort. It is better to use a nonrecursive quicksort simply to guarantee that no stack overflow exception will occur if a worst-case data set is encountered. The merge sort doesn't have this problem, so recursion poses no threat. However, a nonrecursive version does avoid function calls, so I coded two nonrecursive merge sorts. To my surprise, neither of the nonrecursive solutions managed to outperform recursive merge sort.

The first nonrecursive method traverses the list merging all lists of sizes 2, then 4, 8, and so on. It properly handles uneven cases with a minimum of overhead (see Listing Three). The second method is slightly faster, so its times are the ones reported in Figure 1. It is much more complicated. The idea was inspired by the consolidation step of the Fibonacci heap. The idea is to build an array of lists, all initially empty. Each list is responsible for holding the number of nodes in successive powers of 2. You add the nodes from the original list one at a time. Then you add nodes, one at a time, to the 20 list. That list overflows on the second addition, at which point it is moved to the 21 list, emptying the 20 list. Then, if you add another two nodes, the 20 list overflows again. But this time you have to merge it with the existing 21 list. When done, the 21 list has four elements, so it is moved to the 22 list. The procedure is conceptually similar to incrementing a binary number. If there were 15 nodes in total, then the first four lists (20, 21, 22, and 23) would be full. If you then add a 16th node, then successive merge operations would join all nodes into the 24 list, emptying all other lists in the process.

Though more elaborate, this method is faster than the first nonrecursive merge sort because it does not traverse any sublist twice. I also built a second merge function because this sort didn't need some of the parameters and extra work of the recursive sort's merge function. Despite this, the second nonrecursive merge sort did not run faster than the recursive merge sort. The empirical results in Figure 1 show the nonrecursive merge sort to be 0.3 percent slower than the recursive version, but it is really too close to call.

Sort Stability

The merge sort provides stability, a feature that the quicksort doesn't provide without extra programming (including the array sort in the JDK). Stability in this case refers to a sort's ability to keep equivalent keys in the same order that they appeared in the unsorted data. The test program has a few lines of commented code that can be uncommented to demonstrate stability. The test simply adds the field Pos to each node. Before sorting, the numeric position of each node is recorded. After the sort, the key data and Pos value of each node is printed. After the merge sort, the position values for equivalent keys are always ascending, but they are in random orders for the list quicksort. To make a stable quicksort, you could include Pos as a secondary key, but this slows the sort and requires an extra field in the node structure. With the merge sort, stability is free.

Binary Search

According to the empirical results, the linked-list binary search (Listing Four) was the biggest winner. While it's true that a binary search requires sorted order, this is often required anyway. And even when it's not, the results show that, in Java, the cost of sorting is paid for with relatively few searches (for example, about 25 searches on a 4000 element list).

The algorithm starts by setting PartitionFirst equal to the first list element and PartitionSize equal to the number of list nodes. In each iteration of the outer loop, the inner loop traverses to the list's middle node. If the search key is less than the key at the middle node, then the search should continue in the first half of the list. So, the algorithm merely reduces the PartitionSize because the PartitionFirst already refers to the start of the desired sublist. If the search key is greater than the middle node's key, then PartitionFirst is set equal to the node after the middle node, and the PartitionSize is set equal to the count of nodes after the middle node.

On average, the sequential search does n/2 node hops and n/2 comparisons. The number of node hops in a binary search is never less than n/2 but is almost always at or near n. Despite the fact that the binary search does nearly twice as many node hops, the binary search is over nine times faster than a sequential search because the binary search does only log(n) comparisons. The linked-list binary search pays for itself if key comparisons are more complicated than two or three node hops. This is true of many data sets -- for example, search by name requires string comparisons -- but key comparisons are especially costly in Java because compareTo() is a virtual function invocation.

DDJ


Listing One

// Singly Linked List Quicksortprivate Node QuickSort(Node before, Node first, int n) {
  int Num1=0, Num2=n, i=1;
  Node Pivot=first, aNode=first, aNodePrev=first;
  // Pivot Advancement 
  for (i=1; i<n; i++, aNode=aNode.next) {
    if (aNode.compareTo(aNode.next) > 0)
      break;
    if ((i&1)==0) {
      Pivot = Pivot.next;
      Num1++;
    }
  }
  // Recognize sortedness in linear time
  if (i == n) return first;
  // Partition list by unlinking nodes with values less 
  // than the pivot and pushing them onto front of list
  for (aNodePrev = aNode; i < n; i++) {
    aNode = aNodePrev.next;
    if (Pivot.compareTo(aNode) > 0) {
      aNodePrev.next = aNode.next;
      aNode.next = first;
      first = aNode;
      Num1++;
    }
    else aNodePrev = aNode;
  }
  if (before!=null) before.next = first;
  Num2 = n - Num1 - 1;
  // Recurse to sort sublists
  if (Num1 > 1) first = QuickSort(before, first, Num1);
  if (Num2 > 1) QuickSort(Pivot, Pivot.next, Num2);
  return first;
}

Back to Article

Listing Two

// Singly Linked List Recursive Merge Sortprivate void mergesort(Node before, Node F1, int N1, NodePair NP) {
  if (N1 <= 1)
    NP.first = NP.last = F1;
  else {
    Node F2;
    int N2; 
    N2 = N1; N1 >>= 1; N2 -= N1;
    mergesort(before, F1, N1, NP);
    F1 = NP.first;
    F2 = NP.last.next;
    mergesort(NP.last, F2, N2, NP);
    F2 = NP.first;
    merge(before, F1, N1, F2, N2, NP);
  }
}
//==============================================================
private void merge(Node before, Node F1, int N1,
                   Node F2, int N2, NodePair NP) {
  Node first=null, last=null, temp=null;
  int I, J;
  first = last = F1.compareTo(F2) <= 0 ? F1 : F2;
  for (I=J=0; I < N1 || J < N2; ) {
    if (I < N1 && (J>=N2 || F1.compareTo(F2) <= 0))
         { temp = F1; F1 = F1.next; I++; }
    else { temp = F2; F2 = F2.next; J++; }


</p>
    last.next = temp;
    last = temp;
  }
  if (before == null) First = first;
  else before.next = first;
  last.next = F2;
  NP.first = first;
  NP.last = last;       
}

Back to Article

Listing Three

// Simpler Non-recursive Merge Sort// NOTE: Use same merge() as in Listing Two
private void nr2_mergesort() {
  int i, j, k, N1, N2;
  Node F1, F2, before;
  NodePair NP = new NodePair();
  for (i=1; i < NumNodes; i<<=1)
    for (before=null, N1=N2=i, j=0; j+N1<NumNodes; j+=i<<1) {
      F1 = F2 = before==null ? First : before.next;
      for (k=0; k<N1; k++) 
           F2 = F2.next;
      if (N2 > NumNodes-j-N1) 
          N2 = NumNodes-j-N1;     
      merge(before, F1, N1, F2, N2, NP);
      before = NP.last;
    }
}

Back to Article

Listing Four

// Singly Linked List Binary Searchpublic Node binarySearch(Object SearchKey) {
  Node PartitionFirst=First, MidPtr=null;
  int  PartitionSize=NumNodes, Mid, I, Result;
  while (PartitionSize > 0) {
    Mid = PartitionSize / 2;
    MidPtr = PartitionFirst;
    for (I=0; I < Mid; I++)
      MidPtr = MidPtr.next;
    Result = MidPtr.compareTo(SearchKey);
    if (Result > 0)
      PartitionSize = Mid;
    else if (Result < 0) {
      PartitionSize -= Mid;
      PartitionFirst = MidPtr;
    }
    else return MidPtr;         
  }
  return null;
}


</p>

Back to Article


Copyright © 1998, Dr. Dobb's Journal


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.