Algo 1

Below is the syntax highlighted version of ResizingArrayStack.java from §1.3 Stacks and Queues.   Here is the Javadoc.


/*************************************************************************
 *  Compilation:  javac ResizingArrayStack.java
 *  Execution:    java ResizingArrayStack < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
 *  
 *  Stack implementation with a resizing array.
 *
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java ResizingArrayStack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The ResizingArrayStack class represents a last-in-first-out (LIFO) stack
 *  of generic items.
 *  It supports the usual push and pop operations, along with methods
 *  for peeking at the top item, testing if the stack is empty, and iterating through
 *  the items in LIFO order.
 *  

 *  This implementation uses a resizing array, which double the underlying array
 *  when it is full and halves the underlying array when it is one-quarter full.
 *  The push and pop operations take constant amortized time.
 *  The size, peek, and is-empty operations takes
 *  constant time in the worst case. 
 *  

 *  For additional documentation, see Section 1.3 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class ResizingArrayStack implements Iterable {
    private Item[] a;         // array of items
    private int N;            // number of elements on stack


    /**
     * Initializes an empty stack.
     */
    public ResizingArrayStack() {
        a = (Item[]) new Object[2];
    }

    /**
     * Is this stack empty?
     * @return true if this stack is empty; false otherwise
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * Returns the number of items in the stack.
     * @return the number of items in the stack
     */
    public int size() {
        return N;
    }


    // resize the underlying array holding the elements
    private void resize(int capacity) {
        assert capacity >= N;
        Item[] temp = (Item[]) new Object[capacity];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }

    /**
     * Adds the item to this stack.
     * @param item the item to add
     */
    public void push(Item item) {
        if (N == a.length) resize(2*a.length);    // double size of array if necessary
        a[N++] = item;                            // add item
    }

    /**
     * Removes and returns the item most recently added to this stack.
     * @return the item most recently added
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = a[N-1];
        a[N-1] = null;                              // to avoid loitering
        N--;
        // shrink size of array if necessary
        if (N > 0 && N == a.length/4) resize(a.length/2);
        return item;
    }


    /**
     * Returns (but does not remove) the item most recently added to this stack.
     * @return the item most recently added to this stack
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return a[N-1];
    }

    /**
     * Returns an iterator to this stack that iterates through the items in LIFO order.
     * @return an iterator to this stack that iterates through the items in LIFO order.
     */
    public Iterator iterator() {
        return new ReverseArrayIterator();
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ReverseArrayIterator implements Iterator {
        private int i;

        public ReverseArrayIterator() {
            i = N;
        }

        public boolean hasNext() {
            return i > 0;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return a[--i];
        }
    }


    /**
     * Unit tests the Stack data type.
     */
    public static void main(String[] args) {
        ResizingArrayStack s = new ResizingArrayStack();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) s.push(item);
            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
        }
        StdOut.println("(" + s.size() + " left on stack)");
    }
}


Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Mon Oct 7 11:58:25 EDT 2013.

 
Algo 2

Below is the syntax highlighted version of Stack.java from § Algorithms.   Here is the Javadoc.


/*************************************************************************
 *  Compilation:  javac Stack.java
 *  Execution:    java Stack < input.txt
 *
 *  A generic stack, implemented using a singly-linked list.
 *  Each stack element is of type Item.
 *
 *  This version uses a static nested class Node (to save 8 bytes per
 *  Node), whereas the version in the textbook uses a non-static nested
 *  class (for simplicity).
 *  
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java Stack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;


/**
 *  The Stack class represents a last-in-first-out (LIFO) stack of generic items.
 *  It supports the usual push and pop operations, along with methods
 *  for peeking at the top item, testing if the stack is empty, and iterating through
 *  the items in LIFO order.
 *  

 *  This implementation uses a singly-linked list with a static nested class for
 *  linked-list nodes. See {@link LinkedStack} for the version from the
 *  textbook that uses a non-static nested class.
 *  The push, pop, peek, size, and is-empty
 *  operations all take constant time in the worst case.
 *  

 *  For additional documentation, see Section 1.3 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class Stack implements Iterable {
    private int N;                // size of the stack
    private Node first;     // top of stack

    // helper linked list class
    private static class Node {
        private Item item;
        private Node next;
    }

    /**
     * Initializes an empty stack.
     */
    public Stack() {
        first = null;
        N = 0;
    }

    /**
     * Is this stack empty?
     * @return true if this stack is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in the stack.
     * @return the number of items in the stack
     */
    public int size() {
        return N;
    }

    /**
     * Adds the item to this stack.
     * @param item the item to add
     */
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    /**
     * Removes and returns the item most recently added to this stack.
     * @return the item most recently added
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = first.item;        // save item to return
        first = first.next;            // delete first node
        N--;
        return item;                   // return the saved item
    }


    /**
     * Returns (but does not remove) the item most recently added to this stack.
     * @return the item most recently added to this stack
     * @throws java.util.NoSuchElementException if this stack is empty
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return first.item;
    }

    /**
     * Returns a string representation of this stack.
     * @return the sequence of items in the stack in LIFO order, separated by spaces
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    }
       

    /**
     * Returns an iterator to this stack that iterates through the items in LIFO order.
     * @return an iterator to this stack that iterates through the items in LIFO order.
     */
    public Iterator iterator() {
        return new ListIterator(first);
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ListIterator implements Iterator {
        private Node current;

        public ListIterator(Node first) {
            current = first;
        }
        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }


    /**
     * Unit tests the Stack data type.
     */
    public static void main(String[] args) {
        Stack s = new Stack();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) s.push(item);
            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
        }
        StdOut.println("(" + s.size() + " left on stack)");
    }
}



Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Tue Sep 24 10:43:42 EDT 2013.

Algo 3

Below is the syntax highlighted version of Queue.java from § Algorithms.   Here is the Javadoc.


/*************************************************************************
 *  Compilation:  javac Queue.java
 *  Execution:    java Queue < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt  
 *
 *  A generic queue, implemented using a linked list.
 *
 *  % java Queue < tobe.txt 
 *  to be or not to be (2 left on queue)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The Queue class represents a first-in-first-out (FIFO)
 *  queue of generic items.
 *  It supports the usual enqueue and dequeue
 *  operations, along with methods for peeking at the first item,
 *  testing if the queue is empty, and iterating through
 *  the items in FIFO order.
 *  

 *  This implementation uses a singly-linked list with a static nested class for
 *  linked-list nodes. See {@link LinkedQueue} for the version from the
 *  textbook that uses a non-static nested class.
 *  The enqueue, dequeue, peek, size, and is-empty
 *  operations all take constant time in the worst case.
 *  

 *  For additional documentation, see Section 1.3 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class Queue implements Iterable {
    private int N;               // number of elements on queue
    private Node first;    // beginning of queue
    private Node last;     // end of queue

    // helper linked list class
    private static class Node {
        private Item item;
        private Node next;
    }

    /**
     * Initializes an empty queue.
     */
    public Queue() {
        first = null;
        last  = null;
        N = 0;
    }

    /**
     * Is this queue empty?
     * @return true if this queue is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in this queue.
     * @return the number of items in this queue
     */
    public int size() {
        return N;     
    }

    /**
     * Returns the item least recently added to this queue.
     * @return the item least recently added to this queue
     * @throws java.util.NoSuchElementException if this queue is empty
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return first.item;
    }

    /**
     * Adds the item to this queue.
     * @param item the item to add
     */
    public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else           oldlast.next = last;
        N++;
    }

    /**
     * Removes and returns the item on this queue that was least recently added.
     * @return the item on this queue that was least recently added
     * @throws java.util.NoSuchElementException if this queue is empty
     */
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = first.item;
        first = first.next;
        N--;
        if (isEmpty()) last = null;   // to avoid loitering
        return item;
    }

    /**
     * Returns a string representation of this queue.
     * @return the sequence of items in FIFO order, separated by spaces
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    } 

    /**
     * Returns an iterator that iterates over the items in this queue in FIFO order.
     * @return an iterator that iterates over the items in this queue in FIFO order
     */
    public Iterator iterator()  {
        return new ListIterator(first);  
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ListIterator implements Iterator {
        private Node current;

        public ListIterator(Node first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }


    /**
     * Unit tests the Queue data type.
     */
    public static void main(String[] args) {
        Queue q = new Queue();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) q.enqueue(item);
            else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
        }
        StdOut.println("(" + q.size() + " left on queue)");
    }
}


Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Tue Sep 24 09:59:27 EDT 2013.

Algo 4

Below is the syntax highlighted version of Bag.java from § Algorithms.   Here is the Javadoc.


/*************************************************************************
 *  Compilation:  javac Bag.java
 *  Execution:    java Bag < input.txt
 *
 *  A generic bag or multiset, implemented using a singly-linked list.
 *
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java Bag < tobe.txt
 *  size of bag = 14
 *  is
 *  -
 *  -
 *  -
 *  that
 *  -
 *  -
 *  be
 *  -
 *  to
 *  not
 *  or
 *  be
 *  to
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The Bag class represents a bag (or multiset) of 
 *  generic items. It supports insertion and iterating over the 
 *  items in arbitrary order.
 *  

 *  This implementation uses a singly-linked list with a static nested class Node.
 *  See {@link LinkedBag} for the version from the
 *  textbook that uses a non-static nested class.
 *  The add, isEmpty, and size operations
 *  take constant time. Iteration takes time proportional to the number of items.
 *  

 *  For additional documentation, see Section 1.3 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class Bag implements Iterable {
    private int N;               // number of elements in bag
    private Node first;    // beginning of bag

    // helper linked list class
    private static class Node {
        private Item item;
        private Node next;
    }

    /**
     * Initializes an empty bag.
     */
    public Bag() {
        first = null;
        N = 0;
    }

    /**
     * Is this bag empty?
     * @return true if this bag is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in this bag.
     * @return the number of items in this bag
     */
    public int size() {
        return N;
    }

    /**
     * Adds the item to this bag.
     * @param item the item to add to this bag
     */
    public void add(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }


    /**
     * Returns an iterator that iterates over the items in the bag in arbitrary order.
     * @return an iterator that iterates over the items in the bag in arbitrary order
     */
    public Iterator iterator()  {
        return new ListIterator(first);  
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ListIterator implements Iterator {
        private Node current;

        public ListIterator(Node first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }

    /**
     * Unit tests the Bag data type.
     */
    public static void main(String[] args) {
        Bag bag = new Bag();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            bag.add(item);
        }

        StdOut.println("size of bag = " + bag.size());
        for (String s : bag) {
            StdOut.println(s);
        }
    }


}


Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Tue Mar 25 04:52:35 EDT 2014.

Algo 5

Below is the syntax highlighted version of QuickFindUF.java from §1.5 Case Study: Union-Find.   Here is the Javadoc.


/****************************************************************************
 *  Compilation:  javac QuickFindUF.java
 *  Execution:  java QuickFindUF < input.txt
 *  Dependencies: StdIn.java StdOut.java
 *
 *  Quick-find algorithm.
 *
 ****************************************************************************/

/**
 *  The QuickFindUF class represents a union-find data structure.
 *  It supports the union and find operations, along with
 *  methods for determinig whether two objects are in the same component
 *  and the total number of components.
 *  

 *  This implementation uses quick find.
 *  Initializing a data structure with N objects takes linear time.
 *  Afterwards, find, connected, and count
 *  takes constant time but union takes linear time.
 *  

 *  For additional documentation, see Section 1.5 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *     
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class QuickFindUF {
    private int[] id;    // id[i] = component identifier of i
    private int count;   // number of components

    /**
     * Initializes an empty union-find data structure with N isolated components 0 through N-1.
     * @throws java.lang.IllegalArgumentException if N < 0
     * @param N the number of objects
     */
    public QuickFindUF(int N) {
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }

    /**
     * Returns the number of components.
     * @return the number of components (between 1 and N)
     */
    public int count() {
        return count;
    }

    /**
     * Returns the component identifier for the component containing site p.
     * @param p the integer representing one site
     * @return the component identifier for the component containing site p
     * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
     */
    public int find(int p) {
        return id[p];
    }

    /**
     * Are the two sites p and q/tt> in the same component?
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @return true if the two sites p and q are in
     *    the same component, and false otherwise
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
     */
    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }
  
    /**
     * Merges the component containing sitep with the component
     * containing site q.
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
     */
    public void union(int p, int q) {
        if (connected(p, q)) return;
        int pid = id[p];
        for (int i = 0; i < id.length; i++)
            if (id[i] == pid) id[i] = id[q]; 
        count--;
    }

    /**
     * Reads in a sequence of pairs of integers (between 0 and N-1) from standard input, 
     * where each integer represents some object;
     * if the objects are in different components, merge the two components
     * and print the pair to standard output.
     */
    public static void main(String[] args) {
        int N = StdIn.readInt();
        QuickFindUF uf = new QuickFindUF(N);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

}


Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Oct 27 02:13:49 EDT 2013.

/****************************************************************************
 *  Compilation:  javac UF.java
 *  Execution:    java UF < input.txt
 *  Dependencies: StdIn.java StdOut.java
 *  Data files:   http://algs4.cs.princeton.edu/15uf/tinyUF.txt
 *                http://algs4.cs.princeton.edu/15uf/mediumUF.txt
 *                http://algs4.cs.princeton.edu/15uf/largeUF.txt
 *
 *  Weighted quick-union by rank with path compression by halving.
 *
 *  % java UF < tinyUF.txt
 *  4 3
 *  3 8
 *  6 5
 *  9 4
 *  2 1
 *  5 0
 *  7 2
 *  6 1
 *  2 components
 *
 ****************************************************************************/


/**
 *  The UF class represents a union-find data type
 *  (also known as the disjoint-sets data type).
 *  It supports the union and find operations,
 *  along with a connected operation for determinig whether
 *  two sites in the same component and a count operation that
 *  returns the total number of components.
 *  

 *  The union-find data type models connectivity among a set of N
 *  sites, named 0 through N – 1.
 *  The is-connected-to relation must be an 
 *  equivalence relation:
 *  

 *  
 Reflexive: p is connected to p.
 *  
 Symmetric: If p is connected to q,
 *          q is connected to p.
 *  
 Transitive: If p is connected to q
 *          and q is connected to r, then
 *          p is connected to r.
 *  
 *  An equivalence relation partitions the sites into
 *  equivalence classes (or components). In this case,
 *  two sites are in the same component if and only if they are connected.
 *  Both sites and components are identified with integers between 0 and
 *  N – 1. 
 *  Initially, there are N components, with each site in its
 *  own component.  The component identifier of a component
 *  (also known as the root, canonical element, leader,
 *  or set representative) is one of the sites in the component:
 *  two sites have the same component identifier if and only if they are
 *  in the same component.
 *  

 *  
union(p, q) adds a
 *         connection between the two sites p and q.
 *         If p and q are in different components,
 *         then it replaces
 *         these two components with a new component that is the union of
 *         the two.
 *  
find(p) returns the component
 *         identifier of the component containing p.
 *  
connected(p, q)
 *         returns true if both p and q
 *         are in the same component, and false otherwise.
 *  
count() returns the number of components.
 *  
 *  The component identifier of a component can change
 *  only when the component itself changes during a call to
 *  union—it cannot change during a call
 *  to find, connected, or count.
 *  

 *  This implementation uses weighted quick union by rank with path compression
 *  by halving.
 *  Initializing a data structure with N sites takes linear time.
 *  Afterwards, the union, find, and connected 
 *  operations take logarithmic time (in the worst case) and the
 *  count operation takes constant time.
 *  Moreover, the amortized time per union, find,
 *  and connected operation has inverse Ackermann complexity.
 *  For alternate implementations of the same API, see
 *  {@link QuickUnionUF}, {@link QuickFindUF}, and {@link WeightedQuickUnionUF}.
 *
 *  

 *  For additional documentation, see Section 1.5 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */

public class UF {
    private int[] id;     // id[i] = parent of i
    private byte[] rank;  // rank[i] = rank of subtree rooted at i (cannot be more than 31)
    private int count;    // number of components

    /**
     * Initializes an empty union-find data structure with N
     * isolated components 0 through N-1
     * @throws java.lang.IllegalArgumentException if N < 0
     * @param N the number of sites
     */
    public UF(int N) {
        if (N < 0) throw new IllegalArgumentException();
        count = N;
        id = new int[N];
        rank = new byte[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            rank[i] = 0;
        }
    }

    /**
     * Returns the component identifier for the component containing site p.
     * @param p the integer representing one object
     * @return the component identifier for the component containing site p
     * @throws java.lang.IndexOutOfBoundsException unless 0 ≤ p < N
     */
    public int find(int p) {
        if (p < 0 || p >= id.length) throw new IndexOutOfBoundsException();
        while (p != id[p]) {
            id[p] = id[id[p]];    // path compression by halving
            p = id[p];
        }
        return p;
    }

    /**
     * Returns the number of components.
     * @return the number of components (between 1 and N)
     */
    public int count() {
        return count;
    }
  
    /**
     * Are the two sites p and q in the same component?
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @return true if the two sites p and q are in the same component; false otherwise
     * @throws java.lang.IndexOutOfBoundsException unless
     *      both 0 ≤ p < N and 0 ≤ q < N
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

  
    /**
     * Merges the component containing site p with the 
     * the component containing site q.
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @throws java.lang.IndexOutOfBoundsException unless
     *      both 0 ≤ p < N and 0 ≤ q < N
     */
    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) return;

        // make root of smaller rank point to root of larger rank
        if      (rank[i] < rank[j]) id[i] = j;
        else if (rank[i] > rank[j]) id[j] = i;
        else {
            id[j] = i;
            rank[i]++;
        }
        count--;
    }


    /**
     * Reads in a an integer N and a sequence of pairs of integers
     * (between 0 and N-1) from standard input, where each integer
     * in the pair represents some site;
     * if the sites are in different components, merge the two components
     * and print the pair to standard output.
     */
    public static void main(String[] args) {
        int N = StdIn.readInt();
        UF uf = new UF(N);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }
}
Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Oct 27 02:13:49 EDT 2013.

Below is the syntax highlighted version of WeightedQuickUnionUF.java from §1.5 Case Study: Union-Find.   Here is the Javadoc.


/****************************************************************************
 *  Compilation:  javac WeightedQuickUnionUF.java
 *  Execution:  java WeightedQuickUnionUF < input.txt
 *  Dependencies: StdIn.java StdOut.java
 *
 *  Weighted quick-union (without path compression).
 *
 ****************************************************************************/

/**
 *  The WeightedQuickUnionUF class represents a union-find data structure.
 *  It supports the union and find operations, along with
 *  methods for determinig whether two objects are in the same component
 *  and the total number of components.
 *  

 *  This implementation uses weighted quick union by size (without path compression).
 *  Initializing a data structure with N objects takes linear time.
 *  Afterwards, union, find, and connected take
 *  logarithmic time (in the worst case) and count takes constant
 *  time.
 *  

 *  For additional documentation, see Section 1.5 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *     
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class WeightedQuickUnionUF {
    private int[] id;    // id[i] = parent of i
    private int[] sz;    // sz[i] = number of objects in subtree rooted at i
    private int count;   // number of components

    /**
     * Initializes an empty union-find data structure with N isolated components 0 through N-1.
     * @throws java.lang.IllegalArgumentException if N < 0
     * @param N the number of objects
     */
    public WeightedQuickUnionUF(int N) {
        count = N;
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    /**
     * Returns the number of components.
     * @return the number of components (between 1 and N)
     */
    public int count() {
        return count;
    }

    /**
     * Returns the component identifier for the component containing site p.
     * @param p the integer representing one site
     * @return the component identifier for the component containing site p
     * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
     */
    public int find(int p) {
        while (p != id[p])
            p = id[p];
        return p;
    }

    /**
     * Are the two sites p and q in the same component?
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @return true if the two sites p and q
     *    are in the same component, and false otherwise
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

  
    /**
     * Merges the component containing sitep with the component
     * containing site q.
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // make smaller root point to larger one
        if   (sz[rootP] < sz[rootQ]) { id[rootP] = rootQ; sz[rootQ] += sz[rootP]; }
        else                         { id[rootQ] = rootP; sz[rootP] += sz[rootQ]; }
        count--;
    }


    /**
     * Reads in a sequence of pairs of integers (between 0 and N-1) from standard input, 
     * where each integer represents some object;
     * if the objects are in different components, merge the two components
     * and print the pair to standard output.
     */
    public static void main(String[] args) {
        int N = StdIn.readInt();
        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

}



Bottom-up mergesort
  public class MergeBU
  {
     private static Comparable[] aux;      // auxiliary array for merges
     
       public static void merge(Comparable[] a, int lo, int mid, int hi)
  	{  // Merge a[lo..mid] with a[mid+1..hi].
     	int i = lo, j = mid+1;
     	for (int k = lo; k <= hi; k++)  // Copy a[lo..hi] to aux[lo..hi].
      	  aux[k] = a[k];
     	for (int k = lo; k <= hi; k++)  // Merge back to a[lo..hi].
        	if      (i > mid)              a[k] = aux[j++];
        	else if (j > hi )              a[k] = aux[i++];
        	else if (less(aux[j], aux[i])) a[k] = aux[j++];
        	else                           a[k] = aux[i++];
        }

     public static void sort(Comparable[] a)
     {  // Do lg N passes of pairwise merges.
	int N = a.length;
	aux = new Comparable[N];
	for (int sz = 1; sz < N; sz = sz+sz)
                                         // sz: subarray size
	    for (int lo = 0; lo < N-sz; lo += sz+sz) // lo: subarray index
		merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
     } 
}

Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Feb 2 07:38:55 EST 2014.

public class SelectionSortExample
  {
     public static void sort(Comparable[] a)
     {  // Sort a[] into increasing order.
        int N = a.length;               // array length
        for (int i = 0; i < N; i++)
        {  // Exchange a[i] with smallest entry in a[i+1...N).
           int min = i;                 // index of minimal entr.
           for (int j = i+1; j < N; j++)
              if (less(a[j], a[min])) min = j;
           exch(a, i, min);
     }

     }
     private static boolean less(Comparable v, Comparable w)
     {  return v.compareTo(w) < 0;  }

     private static void exch(Comparable[] a, int i, int j)
     {  Comparable t = a[i]; a[i] = a[j]; a[j] = t;  }

     private static void show(Comparable[] a)
     {  // Print the array, on a single line.
        for (int i = 0; i < a.length; i++)
           StdOut.print(a[i] + " ");
        StdOut.println();
     }

     public static boolean isSorted(Comparable[] a)
     {  // Test whether the array entries are in order.
        for (int i = 1; i < a.length; i++)
           if (less(a[i], a[i-1]))  return false;
        return true;
     }

     public static void main(String[] args)
     {  // Read strings from standard input, sort them, and print.
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
     } 
}

Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Feb 2 07:38:55 EST 2014.

public class Example
  {
     public static void sort(Comparable[] a)
     {  // Sort a[] into increasing order.
        int N = a.length;
        for (int i = 1; i < N; i++)
        {  // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
           for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
              exch(a, j, j-1);
        }  
     }

     private static boolean less(Comparable v, Comparable w)
     {  return v.compareTo(w) < 0;  }

     private static void exch(Comparable[] a, int i, int j)
     {  Comparable t = a[i]; a[i] = a[j]; a[j] = t;  }

     private static void show(Comparable[] a)
     {  // Print the array, on a single line.
        for (int i = 0; i < a.length; i++)
           StdOut.print(a[i] + " ");
        StdOut.println();
     }

     public static boolean isSorted(Comparable[] a)
     {  // Test whether the array entries are in order.
        for (int i = 1; i < a.length; i++)
           if (less(a[i], a[i-1]))  return false;
        return true;
     }

     public static void main(String[] args)
     {  // Read strings from standard input, sort them, and print.
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
     } 
}

Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Feb 2 07:38:55 EST 2014.

public class Example
  {
     public static void sort(Comparable[] a)
     {  // Sort a[] into increasing order.
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
        while (h >= 1)
        {  // h-sort the array.
           for (int i = h; i < N; i++)
           {  // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
              for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                 exch(a, j, j-h);
	   }
	   h = h/3; }
     }

     }
     private static boolean less(Comparable v, Comparable w)
     {  return v.compareTo(w) < 0;  }

     private static void exch(Comparable[] a, int i, int j)
     {  Comparable t = a[i]; a[i] = a[j]; a[j] = t;  }

     private static void show(Comparable[] a)
     {  // Print the array, on a single line.
        for (int i = 0; i < a.length; i++)
           StdOut.print(a[i] + " ");
        StdOut.println();
     }

     public static boolean isSorted(Comparable[] a)
     {  // Test whether the array entries are in order.
        for (int i = 1; i < a.length; i++)
           if (less(a[i], a[i-1]))  return false;
        return true;
     }

     public static void main(String[] args)
     {  // Read strings from standard input, sort them, and print.
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
     } 
}


Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Feb 2 07:38:55 EST 2014.

Abstract in-place merge
  public static void merge(Comparable[] a, int lo, int mid, int hi)
  {  // Merge a[lo..mid] with a[mid+1..hi].
     int i = lo, j = mid+1;
     for (int k = lo; k <= hi; k++)  // Copy a[lo..hi] to aux[lo..hi].
        aux[k] = a[k];
     for (int k = lo; k <= hi; k++)  // Merge back to a[lo..hi].
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi )              a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
  }



Top-Down merge sort

public class Merge
  {
     private static Comparable[] aux;      // auxiliary array for merges
     public static void sort(Comparable[] a)
     {
        aux = new Comparable[a.length];    // Allocate space just once.
        sort(a, 0, a.length - 1);
     }
     private static void sort(Comparable[] a, int lo, int hi)
     {  // Sort a[lo..hi].
        if (hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid);       // Sort left half.
        sort(a, mid+1, hi);     // Sort right half.
        merge(a, lo, mid, hi);  // Merge results (code on page 271).
      } 
}

Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Feb 2 07:38:55 EST 2014.

Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Feb 2 07:38:55 EST 2014.

Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Sun Feb 2 07:38:55 EST 2014.