Dr. Dobbs Journal, May 1998, Algorthm Alley, by John Boyer.
// Merge subroutine used by the following 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++; } last.next = temp; last = temp; } if (before = null) First = first else before.next = first; last.next = F2; NP.first = first; NP.last = last; } // Simple non-recursive Merge Sort private void mergesort() { int i, j, k, N1, N2; Node F1, F2, before; NodePair NP = new NodePair(); for (i = 1; i < NumNodes; i <<= 1) { // the { is not required here for (before = null, N1 = N2 = i, j = 0; j+n1<NumNode; j += i << 1) { F1 = F2 = before == null ? First : before.next; for (k = 0; k < N1; k++) F2 = F2.next; // move F2 to [N1] if (N2 > NumNodes - j - N1) N2 = NumNodes - j - N1; // limit N2 merge(before, F1, N1, F2, N2, NP); before = NP.last; } } } // Singly Linked List Recursive Merge Sort private 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); } } // Singly Linked List Binary Search public Node binarySearch(Object SearchKey) { Node PartitionFirst = First, MidPtr = nul; int Partition Size = 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; }
Uses first node's key as the pivot. 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 code deletes aNode by connecting aNodePrev.next to aNode.next. Then aNode is pushed onto the front of the list, becoming the new first node and the remaining nodes of the list are traversed or transferred to the front in the same manner. At the end of this process, the list is divided into two sublists, which can be recursivly sorted by applying this partitioning procedure to each sublist.
//Singly Linked List Quicksort private 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) { //every other time through the loop Pivot=Pivot.next; Num1++; } } //Recognize sortedness in linear time if (i == n) return first; //Pivot advanced through entire list and found it to be aleady sorted // Partition list by unlinking nodes with values less // than the pivot and pushing them onto front of list for (aNodePrev = aNode; i < n; i++) { aNodePrev.next = aNode.next; if (Pivot.compareTo(aNode) > 0) { 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; )
file: /Techref/method/ssllij.htm, 4KB, , updated: 1999/2/20 12:29, local time: 2024/12/23 04:06,
13.59.36.4:LOG IN
|
©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions? <A HREF="http://sxlist.com/Techref/method/ssllij.htm"> Sorting and Searching Linked Lists in Java</A> |
Did you find what you needed? |
Welcome to sxlist.com!sales, advertizing, & kind contributors just like you! Please don't rip/copy (here's why Copies of the site on CD are available at minimal cost. |
Welcome to sxlist.com! |
.