Algorithm Alley

by John Boyer



Listing One

// 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) {

      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;

}



Listing Two

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

  }

}

//==============================================================

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;       

}



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;

    }

}



Listing Four

// Singly Linked List Binary Search

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

}





3



