please dont rip this site

Sorting and Searching Linked Lists in Java

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;
  }

Linked list Quicksort

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;
  )

See also:


file: /Techref/method/ssllij.htm, 4KB, , updated: 1999/2/20 13:29, local time: 2019/9/15 17:01,
TOP NEW HELP FIND: 
3.226.243.10:LOG IN

 ©2019 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?
Please DO link to this page! Digg it! / MAKE! / 

<A HREF="http://www.sxlist.com/techref/method/ssllij.htm"> Sorting and Searching Linked Lists in Java</A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

 

Welcome to sxlist.com!


Site supported by
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 www.sxlist.com!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .