Java Sorting

Selection Sort Algorithm in Java

2010-01-11T11:07:00.000-08:00

The selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2). However, the selection sort can still offer a significant improvement for large records that must be physically moved around in memory, causing the swap time to be much more important than the comparison time. (Typically, this isn’t the case in Java, where references are moved around, not entire objects.)

Selection Sort on the Baseball Players

Let’s consider the baseball players again. In the selection sort, you can no longer compare only players standing next to each other. Thus, you’ll need to remember a certain player’s height; you can use a notebook to write it down. A magenta-colored towel will also come in handy.
A Brief Description
What’s involved in the selection sort is making a pass through all the players and picking (or selecting, hence the name of the sort) the shortest one. This shortest player is then swapped with the player on the left end of the line, at position 0. Now the leftmost player is sorted and won’t need to be moved again. Notice that in this algorithm the sorted players accumulate on the left (lower indices), whereas in the bubble sort they accumulated on the right.
The next time you pass down the row of players, you start at position 1, and, finding the minimum, swap with position 1. This process continues until all the players are sorted.

A More Detailed Description
In more detail, start at the left end of the line of players. Record the leftmost player’s height in your notebook and throw the magenta towel on the ground in front of this person. Then compare the height of the next player to the right with the height in your notebook. If this player is shorter, cross out the height of the first player and record the second player’s height instead. Also move the towel, placing it in front of this new “shortest” (for the time being) player. Continue down the row, comparing each player with the minimum. Change the minimum value in your notebook and move the towel whenever you find a shorter player. When you’re done, the magenta towel will be in front of the shortest player.
Swap this shortest player with the player on the left end of the line. You’ve now sorted one player. You’ve made N-1 comparisons, but only one swap.
On the next pass, you do exactly the same thing, except that you can completely ignore the player on the left because this player has already been sorted. Thus, the algorithm starts the second pass at position 1, instead of 0. With each succeeding pass, one more player is sorted and placed on the left, and one less player needs to be considered when finding the new minimum.

Java Code for Selection Sort

The listing for the selectSort.java program is similar to that for bubbleSort.java, except that the container class is called ArraySel instead of ArrayBub, and the bubbleSort() method has been replaced by selectSort(). Here’s how this method looks:

public void selectionSort()
{
   int out, in, min;
   for(out=0; out// outer loop
   {
      min = out; // minimum
      for(in=out+1; in// inner loop
      if(a[in] < a[min] ) // if min greater,
      min = in; // we have a new min
      swap(out, min); // swap them
   } // end for(out)
} // end selectionSort()

The outer loop, with loop variable out, starts at the beginning of the array (index 0) and proceeds toward higher indices. The inner loop, with loop variable in, begins at out and likewise proceeds to the right.
At each new position of in, the elements a[in] and a[min] are compared. If a[in] is smaller, then min is given the value of in. At the end of the inner loop, min points to the minimum value, and the array elements pointed to by out and min are swapped.

// selectSort.java
// demonstrates selection sort
////////////////////////////////////////////////////////////////
class ArraySel
{
    private long[] a; // ref to array a
    private int nElems; // number of data items
    //--------------------------------------------------------------
    public ArraySel(int max) // constructor
    {
       a = new long[max]; // create the array
       nElems = 0; // no items yet
    }
    //--------------------------------------------------------------
    public void insert(long value) // put element into array
    {
       a[nElems] = value; // insert it
       nElems++; // increment size
    }
    //--------------------------------------------------------------
    public void display() // displays array contents
    {
       for(int j=0; j// for each element,
       System.out.print(a[j] + “ “); // display it
       System.out.println(“”);
    }
    //--------------------------------------------------------------
   public void selectionSort()
    {
       int out, in, min;
       for(out=0; out// outer loop
       {
          min = out; // minimum
          for(in=out+1; in// inner loop
          if(a[in] < a[min] ) // if min greater,
          min = in; // we have a new min
          swap(out, min); // swap them
       } // end for(out)
    } // end selectionSort()
    //--------------------------------------------------------------
    private void swap(int one, int two)
    {
       long temp = a[one];
       a[one] = a[two];
       a[two] = temp;
    }
    //--------------------------------------------------------------
} // end class ArraySel
////////////////////////////////////////////////////////////////
class SelectSortApp
{
   public static void main(String[] args)
   {
      int maxSize = 100; // array size
      ArraySel arr; // reference to array
      arr = new ArraySel(maxSize); // create the array
      arr.insert(77); // insert 10 items
      arr.insert(99);
      arr.insert(44);
      arr.insert(55);
      arr.insert(22);
      arr.insert(88);
      arr.insert(11);
      arr.insert(00);
      arr.insert(66);
      arr.insert(33);
      arr.display(); // display items
      arr.selectionSort(); // selection-sort them
       arr.display(); // display them again
   } // end main()
} // end class SelectSortApp
////////////////////////////////////////////////////////////////

The output from selectSort.java is identical to that from bubbleSort.java:

77 99 44 55 22 88 11 0 66 33
0 11 22 33 44 55 66 77 88 99

Invariant
In the selectSort.java program, the data items with indices less than or equal to out are always sorted.
Efficiency of the Selection Sort
The selection sort performs the same number of comparisons as the bubble sort: N*(N-1)/2. For 10 data items, this is 45 comparisons. However, 10 items require fewer than 10 swaps. With 100 items, 4,950 comparisons are required, but fewer than 100 swaps. For large values of N, the comparison times will dominate, so we would have to say that the selection sort runs in O(N2) time, just as the bubble sort did. However, it is unquestionably faster because there are so few swaps. For smaller values of N, the selection sort may in fact be considerably faster, especially if the swap times are
much larger than the comparison times.

Recursion

2009-12-15T23:39:00.001-08:00

Simply put, recursion is when a function calls itself. That is, in the course of the function definition there is a call to that very same function. At first this may seem like a never ending loop, or like a dog chasing its tail. It can never catch it. So too it seems our method will never finish. This might be true is some cases, but in practise we can check to see if a certain condition is true and in that case exit (return from) our method. The case in which we end our recursion is called a base case . Additionally, just as in a loop, we must change some value and incremently advance closer to our base case.
Consider this function.
void myMethod( int counter) { if(counter == 0) return; else { System.out.println(""+counter); myMethod(--counter); return; } }
This recursion is not infinite, assuming the method is passed a positive integer value. What will the output be?
Consider this method:
void myMethod( int counter) { if(counter == 0) return; else { System.out.println("hello" + counter); myMethod(--counter); System.out.println(""+counter); return; } }

If the method is called with the value 4, what will the output be? Explain.
The above recursion is essentially a loop like a for loop or a while loop. When do we prefer recursion to an iterative loop? We use recursion when we can see that our problem can be reduced to a simpler problem that can be solved after further reduction.
Every recursion should have the following characteristics.

A simple base case which we have a solution for and a return value.
A way of getting our problem closer to the base case. I.e. a way to chop out part of the problem to get a somewhat simpler problem.
A recursive call which passes the simpler problem back into the method.

The key to thinking recursively is to see the solution to the problem as a smaller version of the same problem. The key to solving recursive programming requirements is to imagine that your method does what its name says it does even before you have actually finish writing it. You must pretend the method does its job and then use it to solve the more complex cases. Here is how.
Identify the base case(s) and what the base case(s) do. A base case is the simplest possible problem (or case) your method could be passed. Return the correct value for the base case. Your recursive method will then be comprised of an if-else statement where the base case returns one value and the non-base case(s) recursively call(s) the same method with a smaller parameter or set of data. Thus you decompose your problem into two parts: (1) The simplest possible case which you can answer (and return for), and (2) all other more complex cases which you will solve by returning the result of a second calling of your method. This second calling of your method ( recursion ) will pass on the complex problem but reduced by one increment. This decomposition of the problem will actually be a complete, accurate solution for the problem for all cases other than the base case. Thus, the code of the method actually has the solution on the first recursion.
Let's consider writing a method to find the factorial of an integer. For example 7! equals 7*6*5*4*3*2*1 .
But we are also correct if we say 7! equals 7*6!.
In seeing the factorial of 7 in this second way we have gained a valuable insight. We now can see our problem in terms of a simpler version of our problem and we even know how to make our problem progressively more simple. We have also defined our problem in terms of itself. I.e. we defined 7! in terms of 6!. This is the essence of recursive problem solving. Now all we have left to do is decide what the base case is. What is the simplest factorial? 1!. 1! equals 1.
Let's write the factorial function recursively.
int myFactorial( int integer) { if( integer == 1) return 1; else { return(integer*(myFactorial(integer-1); } }
Note that the base case ( the factorial of 1 ) is solved and the return value is given. Now let us imagine that our method actually works. If it works we can use it to give the result of more complex cases. If our number is 7 we will simply return 7 * the result of factorial of 6. So we actaully have the exact answer for all cases in the top level recursion. Our problem is getting smaller on each recursive call because each time we call the method we give it a smaller number. Try running this program in your head with the number 2. Does it give the right value? If it works for 1 then it must work for two since 2 merely returns 2 * factorial of 1. Now will it work for 3? Well, 3 must return 3 * factorial of 2. Now since we know that factorial of 2 works, factorial of 3 also works. We can prove that 4 works in the same way, and so on and so on.
Food for thought: ask yourself, could this be written iteratively?
Note: make it your habit of writing the base case in the method as the first statement.
Note: Forgetting the base case leads to infinite recursion.
However, in fact, your code won't run forever like an infinite loop, instead, you will eventually run out of stack space (memory) and get a run-time error or exception called a stack overflow. There are several significant problems with recursion. Mostly it is hard (especially for inexperienced programmers) to think recursively, though many AI specialists claim that in reality recursion is closer to basic human thought processes than other programming methods (such as iteration). There also exists the problem of stack overflow when using some forms of recursion (head recursion.) The other main problem with recursion is that it can be slower to run than simple iteration. Then why use it? It seems that there is always an iterative solution to any problem that can be solved recursively. Is there a difference in computational complexity? No.
Is there a difference in the efficiency of execution? Yes, in fact, the recursive version is usually less efficient because of having to push and and pop recursions on and off the run-time stack, so iteration is quicker. On the other hand, you might notice that the recursive versions use fewer or no local variables.
So why use recursion? The answer to our question is predominantly because it is easier to code a recursive solution once one is able to identify that solution. The recursive code is usually smaller, more concise, more elegant, possibly even easier to understand, though that depends on ones thinking style. But also, there are some problems that are very difficult to solve without recursion. Those problems that require backtracking such as searching a maze for a path to an exit or tree based operations (which we will see in semester 2) are best solved recursively. There are also some interesting sorting algorithms that use recursion.

Towers of Hanoi

This problem comes from history, monks in Vietnam were asked to carry 64 gold disks from one tower (stack) to another. Each disk is of a different size. There are 3 stacks, a source stack, a destination stack and an intermediate stack. A disk is placed on one of three stacks but no disk can be placed on top of a smaller disk. The source tower holds 64 disks. How will the monks solve this problem? How long will it take them?
The easiest solution is a recursive one. The key to the solution is to notice that to move any disk, we must first move the smaller disks off of it, thus a recursive definition. Another way to look at it is this, if we had a method to move the top three disks to the middle position, we could put the biggest disk in its place. All we need to do is assume we have this method and then call it.
Lets start with 1 disk (our base case): Move 1 disk from start tower to destination tower and we are done.
To move 2 disks:
Move smaller disk from start tower to intermediate tower, move larger disk from start tower to final tower, move smaller disk from intermediate tower to final tower and we are done.
To move n disks (or think of, say, 3 disks):
Solve the problem for n - 1 disks (i.e. 2 disks) using the intermediate tower instead of the final tower (i.e. get 2 disks onto the intermediate tower). Then , move the biggest disk from start tower to final tower. Then again solve the problem for n - 1 disks but use the intermediate tower instead of the start tower (i.e. get the 2 disks onto the final tower using the start tower as the intermediate tower).

Tail Recursion

Tail recursion is defined as occuring when the recursive call is at the end of the recursive instruction. This is not the case with my factorial solution above. It is useful to notice when ones algorithm uses tail recursion because in such a case, the algorithm can usually be rewritten to use iteration instead. In fact, the compiler will (or at least should) convert the recursive program into an iterative one. This eliminates the potential problem of stack overflow.
This is not the case with head recursion, or when the function calls itself recursively in different places like in the Towers of Hanoi solution. Of course, even in these cases we could also remove recursion by using our own stack and essentially simulating how recursion would work.
In my example of factorial above the compiler will have to call the recursive function before doing the multiplication because it has to resolve the (return) value of the function before it can complete the multiplication. So the order of execution will be "head" recursion, i.e. recursion occurs before other operations.
To convert this to tail recursion we need to get all the multiplication finished and resolved before recursively calling the function. We need to force the order of operation so that we are not waiting on multiplication before returning. If we do this the stack frame can be freed up.
The proper way to do a tail-recursive factorial is this:

int factorial(int number) {
    if(number == 0) {
           return 1;
        }
        factorial_i(number, 1);
}

int factorial_i(int currentNumber, int sum) {
    if(currentNumber == 1) {
        return sum;
    } else {
        return factorial_i(currentNumber - 1, sum*currentNumber);
    }
}

Notice that in the call return factorial_i(currentNumber - 1, sum*currentNumber); both parameters are immediately resolvable. We can compute what each parameter is without waiting for a recursive function call to return. This is not the case with the previous version of factorial. This streamlining enables the compiler to minimize stack use as explained above. Thanks to Jon Bartlett for the example.

Merge Sort Implementation in Java

2009-12-15T23:38:00.000-08:00

In computer science, merge sort or mergesort is a sorting algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order. It is a particularly good example of the divide and conquer algorithmic paradigm. It is a comparison sort.

Conceptually, merge sort works as follows:

Divide the unsorted list into two sublists of about half the size
Sort each of the two sublists
Merge the two sorted sublists back into one sorted list.

The algorithm was invented by John von Neumann in 1945.

The following code shows how to implement merge sort in Java.

    /**
     * Mergesort algorithm.
     * @param a an array of Comparable items.
     */
    public static void mergeSort( Comparable [ ] a ) {
        Comparable [ ] tmpArray = new Comparable[ a.length ];
        mergeSort( a, tmpArray, 0, a.length - 1 );
    }
    
    /**
     * Internal method that makes recursive calls.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param left the left-most index of the subarray.
     * @param right the right-most index of the subarray.
     */
    private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
            int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center );
            mergeSort( a, tmpArray, center + 1, right );
            merge( a, tmpArray, left, center + 1, right );
        }
    }
    
    /**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
            int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd )
            if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            else
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];
        
        while( leftPos <= leftEnd )    // Copy rest of first half
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        
        while( rightPos <= rightEnd )  // Copy rest of right half
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
        
        // Copy tmpArray back
        for( int i = 0; i < numElements; i++, rightEnd-- )
            a[ rightEnd ] = tmpArray[ rightEnd ];
    }

Binary search

2009-12-12T07:06:00.000-08:00

Binary search is one of the fundamental algorithms in computer science. In order to explore it, we'll first build up a theoretical backbone, then use that to implement the algorithm properly and avoid those nasty off-by-one errors everyone's been talking about.

Finding a value in a sorted sequence
In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We'll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.

TDQVEUZ2BQDE

Binary Trees

2009-12-07T04:41:00.000-08:00

Java Binary Trees and Solutions

In Java, the key points in the recursion are exactly the same as in C or C++. In fact, I created the Java solutions by just copying the C solutions, and then making the syntactic changes. The recursion is the same, however the outer structure is slightly different.
In Java, we will have a BinaryTree object that contains a single root pointer. The root pointer points to an internal Node class that behaves just like the node struct in the C/C++ version. The Node class is private -- it is used only for internal storage inside the BinaryTree and is not exposed to clients. With this OOP structure, almost every operation has two methods: a one-line method on the BinaryTree that starts the computation, and a recursive method that works on the Node objects. For the lookup() operation, there is a BinaryTree.lookup() method that the client uses to start a lookup operation. Internal to the BinaryTree class, there is a private recursive lookup(Node) method that implements the recursion down the Node structure. This second, private recursive method is basically the same as the recursive C/C++ functions above -- it takes a Node argument and uses recursion to iterate over the pointer structure.

Java Binary Tree Structure

To get started, here are the basic definitions for the Java BinaryTree class, and the lookup() and insert() methods as examples...
// BinaryTree.java
public class BinaryTree {
// Root node pointer. Will be null for an empty tree.
private Node root;

/*
--Node--
The binary tree is built using this nested node class.
Each node stores one data element, and has left and right
sub-tree pointer which may be null.
The node is a "dumb" nested class -- we just use it for
storage; it does not have any methods.
*/
private static class Node {
Node left;
Node right;
int data;
Node(int newData) {
left = null;
right = null;
data = newData;
}
}

/**
Creates an empty binary tree -- a null root pointer.
*/
public void BinaryTree() {
root = null;
}

/**
Returns true if the given target is in the binary tree.
Uses a recursive helper.
*/
public boolean lookup(int data) {
return(lookup(root, data));
}

/**
Recursive lookup -- given a node, recur
down searching for the given data.
*/
private boolean lookup(Node node, int data) {
if (node==null) {
return(false);
}
if (data==node.data) {
return(true);
}
else if (data return(lookup(node.left, data)); } else { return(lookup(node.right, data)); } }

/** Inserts the given data into the binary tree. Uses a recursive helper. */ public void insert(int data) { root = insert(root, data); } /** Recursive insert -- given a node pointer, recur down and insert the given data into the tree. Returns the new node pointer (the standard way to communicate a changed pointer back to the caller). */ private Node insert(Node node, int data) { if (node==null) { node = new Node(data); } else { if (data <= node.data) { node.left = insert(node.left, data); } else { node.right = insert(node.right, data); } } return(node); // in any case, return the new pointer to the caller }

OOP Style vs. Recursive Style From the client point of view, the BinaryTree class demonstrates good OOP style -- it encapsulates the binary tree state, and the client sends messages like lookup() and insert() to operate on that state. Internally, the Node class and the recursive methods do not demonstrate OOP style. The recursive methods like insert(Node) and lookup (Node, int) basically look like recursive functions in any language. In particular, they do not operate against a "receiver" in any special way. Instead, the recursive methods operate on the arguments that are passed in which is the classical way to write recursion. My sense is that the OOP style and the recursive style do not be combined nicely for binary trees, so I have left them separate. Merging the two styles would be especially awkward for the "empty" tree (null) case, since you can't send a message to the null pointer. It's possible to get around that by having a special object to represent the null tree, but that seems like a distraction to me. I prefer to keep the recursive methods simple, and use different examples to teach OOP. Java Solutions Here are the Java solutions to the 14 binary tree problems. Most of the solutions use two methods:a one-line OOP method that starts the computation, and a recursive method that does the real operation. Make an attempt to solve each problem before looking at the solution -- it's the best way to learn. 1. Build123() Solution (Java) /** Build 123 using three pointer variables. */ public void build123a() { root = new Node(2); Node lChild = new Node(1); Node rChild = new Node(3); root.left = lChild; root.right= rChild; } /** Build 123 using only one pointer variable. */ public void build123b() { root = new Node(2); root.left = new Node(1); root.right = new Node(3); } /** Build 123 by calling insert() three times. Note that the '2' must be inserted first. */ public void build123c() { root = null; root = insert(root, 2); root = insert(root, 1); root = insert(root, 3); } 2. size() Solution (Java) /** Returns the number of nodes in the tree. Uses a recursive helper that recurs down the tree and counts the nodes. */ public int size() { return(size(root)); } private int size(Node node) { if (node == null) return(0); else { return(size(node.left) + 1 + size(node.right)); } } 3. maxDepth() Solution (Java) /** Returns the max root-to-leaf depth of the tree. Uses a recursive helper that recurs down to find the max depth. */ public int maxDepth() { return(maxDepth(root)); } private int maxDepth(Node node) { if (node==null) { return(0); } else { int lDepth = maxDepth(node.left); int rDepth = maxDepth(node.right); // use the larger + 1 return(Math.max(lDepth, rDepth) + 1); } } 4. minValue() Solution (Java) /** Returns the min value in a non-empty binary search tree. Uses a helper method that iterates to the left to find the min value. */ public int minValue() { return( minValue(root) ); } /** Finds the min value in a non-empty binary search tree. */ private int minValue(Node node) { Node current = node; while (current.left != null) { current = current.left; } return(current.data); } 5. printTree() Solution (Java) /** Prints the node values in the "inorder" order. Uses a recursive helper to do the traversal. */ public void printTree() { printTree(root); System.out.println(); } private void printTree(Node node) { if (node == null) return; // left, node itself, right printTree(node.left); System.out.print(node.data + " "); printTree(node.right); } 6. printPostorder() Solution (Java) /** Prints the node values in the "postorder" order. Uses a recursive helper to do the traversal. */ public void printPostorder() { printPostorder(root); System.out.println(); } public void printPostorder(Node node) { if (node == null) return; // first recur on both subtrees printPostorder(node.left); printPostorder(node.right); // then deal with the node System.out.print(node.data + " "); } 7. hasPathSum() Solution (Java) /** Given a tree and a sum, returns true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum. Strategy: subtract the node value from the sum when recurring down, and check to see if the sum is 0 when you run out of tree. */ public boolean hasPathSum(int sum) { return( hasPathSum(root, sum) ); } boolean hasPathSum(Node node, int sum) { // return true if we run out of tree and sum==0 if (node == null) { return(sum == 0); } else { // otherwise check both subtrees int subSum = sum - node.data; return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum)); } } 8. printPaths() Solution (Java) /** Given a binary tree, prints out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work. */ public void printPaths() { int[] path = new int[1000]; printPaths(root, path, 0); } /** Recursive printPaths helper -- given a node, and an array containing the path from the root node up to but not including this node, prints out all the root-leaf paths. */ private void printPaths(Node node, int[] path, int pathLen) { if (node==null) return; // append this node to the path array path[pathLen] = node.data; pathLen++; // it's a leaf, so print the path that led to here if (node.left==null && node.right==null) { printArray(path, pathLen); } else { // otherwise try both subtrees printPaths(node.left, path, pathLen); printPaths(node.right, path, pathLen); } } /** Utility that prints ints from an array on one line. */ private void printArray(int[] ints, int len) { int i; for (i=0; i System.out.print(ints[i] + " "); } System.out.println(); } 9. mirror() Solution (Java) /** Changes the tree into its mirror image. So the tree... 4 / \ 2 5 / \ 1 3 is changed to... 4 / \ 5 2 / \ 3 1 Uses a recursive helper that recurs over the tree, swapping the left/right pointers. */ public void mirror() { mirror(root); } private void mirror(Node node) { if (node != null) { // do the sub-trees mirror(node.left); mirror(node.right); // swap the left/right pointers Node temp = node.left; node.left = node.right; node.right = temp; } } 10. doubleTree() Solution (Java) /** Changes the tree by inserting a duplicate node on each nodes's .left. So the tree... 2 / \ 1 3 Is changed to... 2 / \ 2 3 / / 1 3 / 1 Uses a recursive helper to recur over the tree and insert the duplicates. */ public void doubleTree() { doubleTree(root); } private void doubleTree(Node node) { Node oldLeft; if (node == null) return; // do the subtrees doubleTree(node.left); doubleTree(node.right); // duplicate this node to its left oldLeft = node.left; node.left = new Node(node.data); node.left.left = oldLeft; } 11. sameTree() Solution (Java) /* Compares the receiver to another tree to see if they are structurally identical. */ public boolean sameTree(BinaryTree other) { return( sameTree(root, other.root) ); } /** Recursive helper -- recurs down two trees in parallel, checking to see if they are identical. */ boolean sameTree(Node a, Node b) { // 1. both empty -> true if (a==null && b==null) return(true); // 2. both non-empty -> compare them else if (a!=null && b!=null) { return( a.data == b.data && sameTree(a.left, b.left) && sameTree(a.right, b.right) ); } // 3. one empty, one not -> false else return(false); } 12. countTrees() Solution (Java) /** For the key values 1...numKeys, how many structurally unique binary search trees are possible that store those keys? Strategy: consider that each value could be the root. Recursively find the size of the left and right subtrees. */ public static int countTrees(int numKeys) { if (numKeys <=1) { return(1); } else { // there will be one value at the root, with whatever remains // on the left and right each forming their own subtrees. // Iterate through all the values that could be the root... int sum = 0; int left, right, root; for (root=1; root<=numKeys; root++) { left = countTrees(root-1); right = countTrees(numKeys - root); // number of possible trees with this root == left*right sum += left*right; } return(sum); } } 13. isBST1() Solution (Java) /** Tests if a tree meets the conditions to be a binary search tree (BST). */ public boolean isBST() { return(isBST(root)); } /** Recursive helper -- checks if a tree is a BST using minValue() and maxValue() (not efficient). */ private boolean isBST(Node node) { if (node==null) return(true); // do the subtrees contain values that do not // agree with the node? if (node.left!=null && maxValue(node.left) > node.data) return(false); if (node.right!=null && minValue(node.right) <= node.data) return(false); // check that the subtrees themselves are ok return( isBST(node.left) && isBST(node.right) ); } 14. isBST2() Solution (Java)/** Tests if a tree meets the conditions to be a binary search tree (BST). Uses the efficient recursive helper. */ public boolean isBST2() { return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) ); } /** Efficient BST helper -- Given a node, and min and max values, recurs down the tree to verify that it is a BST, and that all its nodes are within the min..max range. Works in O(n) time -- visits each node only once. */ private boolean isBST2(Node node, int min, int max) { if (node==null) { return(true); } else { // left should be in range min...node.data boolean leftOk = isBST2(node.left, min, node.data); // if the left is not ok, bail out if (!leftOk) return(false); // right should be in range node.data+1..max boolean rightOk = isBST2(node.right, node.data+1, max); return(rightOk); } } by Nick Parlante

Java, sorting, ArrayList example, generics

2009-12-03T23:33:00.000-08:00

A Java ArrayList holds an ordered sequence of items like an array, but there are differences:

1. An ArrayList has no fixed size but can be extended by adding elements later
2. An ArrayList can only hold objects (not primitives)
3. ArrayList elements are addressed by methods and not by square bracket notation.

Here's an example from yesterday - showing a typical use of an ArrayList; I was reading a file but didn't know how many lines it contained, so an ArrayList gave me the flexibility I needed.

import java.io.*;
import java.util.*;

public class Pesort {

public static void main (String [] args) throws Exception {

// Following line up to Java 1.4 then gives warnings
//ArrayList Stuff = new ArrayList();

// OR following line from Java 1.5;
// this specifies that the ArrayList is to contain Strings

ArrayList  Stuff = new ArrayList();

// Above lines show use of "Generics" - compare to
// Templates in C++

BufferedReader Source = new BufferedReader(
new FileReader("../request.txt"));

System.out.println("---------- UnSorted");

while (Source.ready() ) {
String Line = Source.readLine();  
System.out.println(Line);
Stuff.add(Line);
}

System.out.println("---------- Alphabetic Sort");

Collections.sort(Stuff);

Iterator stepper = Stuff.iterator();
while (stepper.hasNext()) {
String current = (String)stepper.next();
System.out.println(current);
}


System.out.println("---------- Sort by line length");

Collections.sort(Stuff, new byLineLength());

stepper = Stuff.iterator();
while (stepper.hasNext()) {
String current = (String)stepper.next();
System.out.println(current);
}
}

}

Here are the results from running that program:

[trainee@snowdrop java08]$ java Pesort
---------- UnSorted
antonia Perl XML PHP Tcl/Tk MySQL
barbara Tcl/Tk ASP Ruby Java
cherry Perl Java Ruby MySQL
delia XML PHP Java ASP
florence Ruby PHP Java ASP
gloria XML Perl Tcl/Tk MySQL
zoe Ruby ASP Perl PHP
adam Tcl/Tk Perl Python MySQL
barry Python XML Java Perl PHP
charles Perl Ruby MySQL Tcl/Tk
ed Ruby Perl Java PHP
fred MySQL Perl Java XML
graham Java Perl Tcl/Tk
harry PHP Python Java
ivan Ruby Java Perl Tcl/Tk MySQL
victor Ruby Perl Tcl/Tk MySQL
william Ruby Perl PHP
xavier PHP Java Perl
yuri XML PHP Perl Tcl/Tk
zachary MySQL Java Tcl/Tk
---------- Alphabetic Sort
adam Tcl/Tk Perl Python MySQL
antonia Perl XML PHP Tcl/Tk MySQL
barbara Tcl/Tk ASP Ruby Java
barry Python XML Java Perl PHP
charles Perl Ruby MySQL Tcl/Tk
cherry Perl Java Ruby MySQL
delia XML PHP Java ASP
ed Ruby Perl Java PHP
florence Ruby PHP Java ASP
fred MySQL Perl Java XML
gloria XML Perl Tcl/Tk MySQL
graham Java Perl Tcl/Tk
harry PHP Python Java
ivan Ruby Java Perl Tcl/Tk MySQL
victor Ruby Perl Tcl/Tk MySQL
william Ruby Perl PHP
xavier PHP Java Perl
yuri XML PHP Perl Tcl/Tk
zachary MySQL Java Tcl/Tk
zoe Ruby ASP Perl PHP
---------- Sort by line length
xavier PHP Java Perl
ed Ruby Perl Java PHP
harry PHP Python Java
william Ruby Perl PHP
zoe Ruby ASP Perl PHP
delia XML PHP Java ASP
graham Java Perl Tcl/Tk
fred MySQL Perl Java XML
yuri XML PHP Perl Tcl/Tk
zachary MySQL Java Tcl/Tk
florence Ruby PHP Java ASP
cherry Perl Java Ruby MySQL
barbara Tcl/Tk ASP Ruby Java
gloria XML Perl Tcl/Tk MySQL
adam Tcl/Tk Perl Python MySQL
victor Ruby Perl Tcl/Tk MySQL
barry Python XML Java Perl PHP
charles Perl Ruby MySQL Tcl/Tk
ivan Ruby Java Perl Tcl/Tk MySQL
antonia Perl XML PHP Tcl/Tk MySQL
[trainee@snowdrop java08]$

And here is the comparator class that I wrote for my non-standard sort. Using a comparator class, the programmer can provide a method which is used internally by the sort method to compare two items and return an integer - negative, nought or positive - to indicate if the first object comes first in sequence, the objects have the same tank, or it comes second.

public class byLineLength implements java.util.Comparator {
public int compare(Object boy, Object girl) {
int sdif = ((String)boy).length() - ((String)girl).length();
return sdif;
}
}

partitioning sorting code

2009-12-01T00:10:00.001-08:00

public int partition(int left, int right, int pivot)
{
int leftIdx = left -1;
int rightIdx = right + 1;
while (true)
{
while(leftIdx < right && data[++leftIdx] < pivot)
; //No operation, just increase the pointer
while( rightIdx > left && data[--rightIdx]>pivot)
;
if(leftIdx >= rightIdx)
break;
else
swap(leftIdx, rightIdx);
}
return leftIdx;
}

shell sorting code

2009-12-01T00:09:00.000-08:00

public void shellSort()
{
int inner, outer;
int temp;

//Knuth’s recursion for initial interval sequence
int h = 1;
while(h<=aSize/3)
h = h*3 + 1;

//At each gap interval step
while(h>0)
{
//Arrange each subset with insertion sorting
//Start comparing the second element of the
//subset to the first one
for(outer=h;outer {
//Make a copy of the first element
//not yet sorted
temp = data[outer];
inner = outer;

//And compare to all elements of the same
//subset that have been sorted already
while(inner > h-1 && data[inner – h] >= temp)
{
//move bigger values forward h steps
data[inner] = data[inner - h];
inner -= h;
}
//and insert the not sorted element on its
place
data[inner] = temp;
}
//Next interval in the sequence
h = (h-1)/3;
}
}

insertion code

2009-12-01T00:08:00.000-08:00

The algorithm implementation for the Java Array class could be like the following:
public void insertionSort()
{
int i,j;
for(i=1; i {
int temp = data[i];
j = i;
while (j>0 && data[j-1] >= temp)
{
data[j] = data[j-1];
--j;
}
data[j]=temp;
}
}

selection sort code

2009-12-01T00:07:00.002-08:00

The implementation of the selection sort algorithm in our Array class could look like this:
public void selectSort()
{
int i,j,min;
for (i=0;i
{
min=i; //The first element is the first minimum

for (j = i+1;j

if(data[j] < data[min])//if new item smaller

min = j;//It is the new minimum

swap(i,min);
}
}

or you can see example from this video from youtube
watch me

bubble sort code

2009-12-01T00:07:00.001-08:00

The bubble sort algorithm for an integer array class with Java language is presented below. The
sorting algorithm applies the private method swap in the operation.
public void bubbleSort()
{
int i,j;
for (i=aSize; i>1; i--)
for(j=0;j if(array[j] > array[j+1])
swap(j,j+1);
}

private void swap(int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

Collections methods

2009-11-30T12:19:00.001-08:00

The java.util.Collections class contains static utility methods for manipulating collections.

Some useful Collections methods

Assume the following declarations have been made, where T is a class or interface type.

   int i;
  List listC;   // List of the Comparable objects.
  List list;    // Any kind of list.  Need not be Comparable.
  Comparator comp;
  T key;
  T t;
  Collection coll;  // Any kind of Collection (List, Set, Deque).
  Collection collC; // Any kind of Collection implementing Comparable.

Rearranging - Sorting, Shuffling, . . .
	`Collections.sort(listC)`	Sorts `listC`. Elements must be Comparable. Stable, O(N log N).
	`Collections.sort(list, comp)`	Sorts `list` using a comparator.
	`Collections.shuffle(list)`	Puts the elements of `list` in random order.
	`Collections.reverse(list)`	Reverses the elements of `list`.
Searching
`i =`	`Collections.binarySearch(listC, key)`	Searches `list` for `key`. Returns index of element or negative value if not found. See Binary Search.
`i =`	`Collections.binarySearch(list, key, comp)`	Searches in `list` for `key` using Comparator comp.
`t =`	`Collections.max(collC)`	Returns maximum valued Comparable object in `collC`.
`t =`	`Collections.max(coll, comp)`	Maximum valued object in `coll` using Comparator `comp`.
`t =`	`Collections.min(collC)`	Returns minimum valued Comparable object in `collC`.
`t =`	`Collections.min(coll, comp)`	Minimum valued object in `coll` using Comparator `comp`.

There are many additional methods in Collections, but the above are a good start.

Searching may also be implemented in data structure classes

All List and Set classes implement the contains() method, which performes a linear search on lists (O(N)), a binary search for TreeSets (O(log N)), and a hashed search for HashSets (O(1)).

Maps define get() to search for the key. For HashMaps the search is O(1), and for TreeMaps the search is O(log N).

Sorting may be implicit in a data structure class

TreeSet data and TreeMap keys are sorted at all times. They are implemented as binary trees, so insertion and search are both O(log N). An iterator can be used to get retrieve the data (TreeSets) or keys (TreeMaps) in sorted order. Either the element class must be Comparable, or a Comparator must be supplied.

2009-11-30T12:17:00.001-08:00

Array Library Methods

Static methods for manipulating arrays are available in the java.util.Arrays and java.System classes. Assume the following declarations, where T is the array element type, either a primitive, object or either kind of type depending on which method is being called.

T       x, key;  // This type T can be either a primitive or object type.
T[]     a, a2;   // This type T can be either a primitive or object type.
List lst;     // Only object types T.
Comparator comp;  // Only object types T.
int     i;    // Index returned from search.
int     i1, i2;
int     from; // Lower bound of subscript range.  Includes this element.
int     to;   // Upper bound of subscript range.  Does not include this element.
String  s;
boolean b;  // Normally the method result will be used in an if.

`lst =`	`Arrays.asList(a);`	List based on the array.
`s =`	`Arrays.toString(a);`	String form surrounded by "[]", elements separated by ", ".
`s =`	`Arrays.deepToString(a);`	String form by recursively converting subarrays.
`b =`	`Arrays.equals(a, a2);`	True if arrays are same size and all elements are equal (== or equals as appropriate).
`b =`	`Arrays.deepEquals(a, a2);`	As above, recursively applied to subarrays.
	`Arrays.fill(a, x);`	Fills array with a value.
	`Arrays.fill(a, from, to, x);`	Fills subrange (from inclusive, to exclusive) with a value.
Making a copy of part of an array
	`System.arraycopy(a, i1, a2, i2, len);`	Shallow copy len elements from `a[i1]` to `a2[i2]`. Case!
`a2 =`	`Arrays.copyOf(a, newLength);`	New shallow copy of array with new length. If longer, uses default values.
`a2 =`	`Arrays.copyOfRange(a, from, to);`	New shallow copy of portion of array.
Searching
`i =`	`Arrays.binarySearch(a, key);`	A O(log N)search of array sorted in ascending order. If the key is not found, a negative number, -insertionPoint-1, is returned.
`i =`	`Arrays.binarySearch(a, key, comp);`	Binary search of a sorted array of objects (not primitives).

	`Arrays.sort(a);`	Sorts in "natural" order. If object type, elements must be comparable.
	`Arrays.sort(a, comp);`	Sorts objects (not primitives) using comparator.
	`Arrays.sort(a, from, to);`	Sorts subrange, including `a[from]` excluding `a[to]`.
	`Arrays.sort(a, from, to, comp);`	Sorts objects (not primitives) in subrange using comparator.

Use `java.util.Arrays.toString(...)` for debugging

AVOID default toString(). Using the common debugging technique of printing intermediate values on the console with arrays is good, but requires calling a library method to get the results you expect. Arrays are a subclass of Object as ever other object is, and therefore the toString() method is defined for every array. The results will very likely disappoint you.

String[] abc = {"a", "b", "c"};
System.out.println(abc);   // println calls toString() on object parameters.

This displays the relatively unhelpful "[L", element type, ";@", and hexadecimal memory address of the array.

[Ljava.lang.String;@f6f1b6

USE java.util.Arrays.toString(...) and you'll get something much more readable. An import java.util.*; statement avoids the extra package qualifier.

String[] abc = {"a", "b", "c"};
System.out.println(java.util.Arrays.toString(abc));

This produces the following output, which is the same as toString() applied to a List.

[a, b, c]

Use `Arrays.asList(...)` for Collections view of array

Make a list. The Arrays class has some useful methods for working with arrays, but there are a lot more if you make your array look like a List. The Collections class has many useful methods, eg, shuffle, reverse, max, ....

import java.util.*;
   . . .
   List listabc = Arrays.asList(abc); 
   // The Collections methods can now be use with listabc.

View of underlying array. The list that is created is not a regular ArrayList. It is based only on the original array, so you can't do things like adding elements to the list because this would cause reallocation of a larger underlying array.

Uses the underlying array. One of the really nice things about this is that you can still use the underlying array, which means that creating this list doesn't prevent you from taking advantage of the efficiency of array access for example.

Objects only. The java.util.Arrays.asList(...) method only works for arrays of object types. If you try to use it with an array of primitives, you will get a compilation error.

Shuffling (randomizing) an array

import java.util.*;
. . .
   List labc = Arrays.asList(abc);
   . . .
   Collections.shuffle(labc);
   System.out.println(labc);

Which gave the following output. Note that the List overrides toString() to give reasonable output.

[b, a, c]

Inefficient? Not necessarily. Constructing a new List object from the array is only inefficient if you're doing it frequently. If you do it very often then you want to avoid creating a new list each time. Creating the list one time is not a problem because the list that is produced is backed by this one array -- you can change elements in the array and the list will reflect those changes.

Searching and Sorting Overview

2009-11-30T12:16:00.000-08:00

Why searching and sorting are often treated together

Searching and sorting algorithms are often grouped together for a couple of reasons.

Comparisons are used by both types of algorithms.
Searching often requires a data structure that is already sorted.
Searching and sorting are common operations on data structures.

Comparing 3 ways - Operators, Comparable, Comparator

Comparisons are at the heart of both searching and sorting. Comparison turns out not to be quite as simple as it first appears to be. There are three ways values can be compared.

Comparison operators (< <= == != >= >) for primitive values.
```
    if (a <>     
```
Implementing the Comparable interface requires defining a compare() method. Java classes that have a natural sorting order (eg, String) often implement Comparable. That Comparable is implemented as an instance method of the class that is being compared (in contrast to Comparator).
```
    if (s.compareTo(t) <>         
```
Implementing the Comparator interface requires defining a the compare() method. This method is not defined in the classes that are being compared, but usually in a small utility class which only defines this method. Comparators are very useful for classes that can be sorted in multiple ways.
```
    if (comparator.compare(x, y) <>         
```

Use predefined sorting and searching methods if possible.

Java defines a number of searching and sorting methods. You should always use these in preference to writing your own because the library methods are almost always faster and have been well tested. However, there are times that the predefined methods don't work for your data structures, so it's also good to understand how these algorithms work.

Predefined sorting and searching methods for arrays

See Array Library Methods for a brief description of the static Array.binarySearch() and Array.sort() methods.

Predefined sorting and searching in the Collections classes

See Collections Class for a brief description of the static Collections.binarySearch() and Collections.sort() methods. This also has a brief discussion of data structures classes which are automatically sorted (those based on trees), or which have better than linear search methods (based on trees or hashing).

Algorithms: Recursive Binary Search

2009-11-30T12:15:00.001-08:00

Recursive Binary Search

Iterative algorithms, ie those with a loop, can usually be easily rewritten to use recursive method calls instead of loops. However the iterative version is usually simpler, faster, and uses less memory.

Some problems, eg traversing a tree, are better solved recursively because the recursive solution is so clear (eg, binary tree traversal). Iterative binary search is more efficient than the recursive form, but it is one of the more plausible algorithms to use as an illustration of recursion.

This recursive version checks to see if we're at the key (in which case it can return), otherwise it calls itself to solve a smaller problem, ie, either the upper or lower half of the array.

Example

/** Recursive binary search of sorted array.    Negative value on failure.
*  The upperbound index is not included in the search.
*  This is to be consistent with the way Java in general expresses ranges.
*  The performance is O(log N).
*  @param sorted Array of sorted values to be searched.
*  @param first Index of beginning of range.  First element is a[first].
*  @param upto  Last element that is searched is sorted[upto-1].
*  @param key   Value that is being looked for.
*  @return      Returns index of the first match, or or -insertion_position
*               -1 if key is not in the array. This value can easily be
*               transformed into the position to insert it.
*/
public static int rBinarySearch(int[] sorted, int first, int upto, int key) {
  
   if (first < upto) {
       int mid = first + (upto - first) / 2;  // Compute mid point.
       if (key < sorted[mid]) {
           return rBinarySearch(sorted, first, mid, key);
          
       } else if (key > sorted[mid]) {
           return rBinarySearch(sorted, mid+1, upto , key);
          
       } else {
           return mid;   // Found it.
       }
   }
   return -(first + 1);  // Failed to find key
}

Algorithms: Linear Search

2009-11-30T12:14:00.001-08:00

Look at every element

This is a very straightforward loop comparing every element in the array with the key. As soon as an equal value is found, it returns. If the loop finishes without finding a match, the search failed and -1 is returned.

Performance

For small arrays, linear search is a good solution because it's so straightforward. In an array of a million elements linear search on average will take 500,000 comparisons to find the key. For a much faster search, take a look at binary search.

Example

/** Linear search of array for key.  Returns index or -1 if not found.
*  The upperbound index is not included in the search.
*  This is to be consistent with the way Java in general expresses ranges.
*  This searches from low to high index values.
*  The performance is O(N).
*  @param a Array of values to be searched.
*  @param first Index of beginning of range.  First element is a[first].
*  @param upto  Last element that is searched is a[upto-1].
*  @param key   Value that is being looked for.
*  @return      Returns index of the first match, or -1 if no match.
*/
public static int linearSearch(int[] a, int first, int upto, int key) {
  
   for (int i = first; i < upto; i++) {
       if (key == a[i]) {
           return i;  // Found key, return index.
       }
   }
   return -1;        // Failed to find key
}

Algorithms: Binary Search

2009-11-30T12:13:00.000-08:00

Divide in half

A fast way to search a sorted array is to use a binary search. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.

Performance

The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.

This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, O(N log N), it may not be worth the effort to sort when there are only a few searches.

Example

//=========================================================== binarySearch
/** Binary search of sorted array.  Negative value on search failure.
*  The upperbound index is not included in the search.
*  This is to be consistent with the way Java in general expresses ranges.
*  The performance is O(log N).
*  @param sorted Array of sorted values to be searched.
*  @param first Index of first element to serach, sorted[first].
*  @param upto  Index of last element to search, sorted[upto-1].
*  @param key   Value that is being looked for.
*  @return      Returns index of the first match, or or -insertion_position
*               -1 if key is not in the array. This value can easily be
*               transformed into the position to insert it.
*/
public static int binarySearch(int[] sorted, int first, int upto, int key) {
  
   while (first < upto) {
       int mid = (first + upto) / 2;  // Compute mid point.
       if (key < sorted[mid]) {
           upto = mid;     // repeat search in bottom half.
       } else if (key > sorted[mid]) {
           first = mid + 1;  // Repeat search in top half.
       } else {
           return mid;     // Found it. return position
       }
   }
   return -(first + 1);    // Failed to find key
}

Style violation? Note: this code violates the advice of not altering method parameters. The reason is that it can under some circumstances make the code less readable. In this case, however, the code would probably be less readable by introducing two extra local variables.

Computing the midpoint

There are two common ways to compute the index of the middle element. The most common way is to add the lowest and hightest and divide by two. For example,

int mid = (first + last) + 2;

Overflow. This works well, or at least has worked well, until recently. The problem appeared when memories, and arrays, got very large. For the first time the sum of two array indexes, an intermediate value in the computation, can overflow the size of an int. Computing the midpoint by adding the two and then dividing doesn't work.

Reordering the expession avoids overflow. The solution is to rewrite the expression so that no intermediate value overflows the size of an int. This is easy to do using the following.

int mid = first + (last - first) / 2;

For most programs the difference between the two computations will never be seen because it will only appeaer with very large arrays.

Variation on binary search

The following method shows another version of a binary search method: (1) it compares elements of a string array (so comparisons use the compareTo() method), and (2) it sorts the entire array so fewer parameters are supplied, and therefore local variables are declared to take their place.

public static int binarySearch(String[] sorted, String key) {
   int first = 0;
   int upto  = sorted.length;
  
   while (first < upto) {
       int mid = (first + upto) / 2;  // Compute mid point.
       if (key.compareTo(sorted[mid]) < 0) {
           upto = mid;       // repeat search in bottom half.
       } else if (key.compareTo(sorted[mid]) > 0) {
           first = mid + 1;  // Repeat search in top half.
       } else {
           return mid;       // Found it. return position
       }
   }
   return -(first + 1);      // Failed to find key
}

Sorting Effectively in Java

2009-11-30T11:31:00.000-08:00

This tutorial is generally about sorting in Java – ways to do it, and how to do it correctly, quickly, and effectively. This tutorial will use one problem, and shows the many approaches to do so.

Here’s the problem:
Suppose you’re to sort a list of books, given by the number of pages, and the initial of the author. The style of input is on one line, a number between 0 – 999 denoting the number of pages, a space, then the author’s initials with 2 uppercase letters.

We are to sort them by the number of pages, and then by the first, then last initials of the author.

The input will be given by one string, with one number denoting the number of books. We’re to implement a “bookOrder” method that returns the sorted string.

Input:
15 AB 219 AE 518 SE 518 AB 17 CE, 5

Output:
15 AB 17 CE 219 AE 518 AB 518 SE

Method 1
Because in competitions, this is timed, so one might write it very inefficently, using bubblesort:

import java.util.*;
public class Book{
   public String bookOrder( String books, int number ){
      
   int[] pages = new int[ number ];
   String[] title = new String[ number ];
   StringTokenizer st = new StringTokenizer( books );

   // Parsing
   for ( int i = 0; i < number; i++ ){
       pages[i] = Integer.parseInt( st.nextToken() );
       title[i] = st.nextToken();
   }

   // Bubblesort
   for ( int i = 0; i < number; i++ ){
       for ( int j = 0; j < number - 1; j++ ){
       // This does the actual comparison
       if ( pages[j] > pages[j+1] ||
           ( pages[j] == pages[j+1] && title[j].compareTo( title[j+1] ) > 0 ) ){
           // Swapping
           pages[j] ^= pages[j+1];
           pages[j+1] ^= pages[j];
           pages[j] ^= pages[j+1];
           String temp = title[j];
           title[j] = title[j+1];
           title[j+1] = temp;
       }
       }
   }

   // Returns it in the format required.    
   String s = "";
   for ( int i = 0; i < number; i++ ){
       s += (int)pages[i] + " " + title[i] + " ";
   }
   // trim() trims the trailing ( and leading spaces ) in a string.
       return s.trim();
   }
}

The above method took about 5 minutes to write, is stable, but isn't very efficient. ( At O( n^2 ) )

This code is also very flexible, as you only need to change this statement to sort it differently:

if ( pages[j] > pages[j+1] ||
( pages[j] == pages[j+1] && title[j].compareTo( title[j+1] ) > 0 ) )

If we wanted to sort by initial first and then page number, we can easily modified this to:

if ( title[j].compareTo( title[j+1] ) > 0 ) ||
( title[j].compareTo( title[j+1] ) == 0 && pages[j] > pages[j+1] ) )

or changed the signs if we wanted to sort descendingly:

if ( pages[j] < pages[j+1] ||
( pages[j] == pages[j+1] && title[j].compareTo( title[j+1] ) > 0 ) )

Method 2
A better and more efficient way is to use the Java API. This is using a relatively underused class java.util.Arrays and the interface Comparable:

import java.util.*;
public class Book{
   private class B implements Comparable {
   // Fields to be sorted
   int pages;
   String title;
  
   // Initializer
   public B ( int p, String t ){
       title = t;
       pages = p;
   }
  
   // The required compareTo method.
   public int compareTo( Object o ){
       B k = (B) o;
       if ( pages != k.pages ){
       return pages - k.pages;
       }
       else
       return title.compareTo( k.title );
   }
   }

   public String bookOrder( String books, int number ){
   B[] book = new B[ number ];
   StringTokenizer st = new StringTokenizer( books );

   // Parsing
   for ( int i = 0; i < number; i++ ){
       book[i] = new B(Integer.parseInt( st.nextToken() ), st.nextToken() );
   }
  
   // Using Arrays.sort
   Arrays.sort( book );
  
   // Return it in the format required.
   String s = "";
   for ( int i = 0; i < number; i++ ){
       s += (int)book[i].pages + " " + book[i].title + " ";
   }
   return s.trim();
   }
}

This ensures that it runs in O( n * log n ) time, using a tuned quicksort. The best thing about writing
the code this way is that it's cleaner, and it's also less error-prone, if you let the API do the work.

Let's go over it in detail:

private class B implements Comparable

This is a private helper class. It implements Comparable so that we can sort it later.

public int compareTo( Object o ){
   B k = (B) o;
   if ( pages != k.pages ){
   return pages - k.pages;
   }
   else
   return title.compareTo( k.title );
}

This method is the method that does the comparing. Naturally, it returns a negative integer if this object is smaller, a zero if they're the same, and a positive interger if the specified Object is smaller.

Arrays.sort( Object[] )

This lets us sort anything, but it requires that all elements in the array be implementing the Comparable interface. That means if you're sorting just ints, or doubles, or Strings, this is very handy and let you get the work done quicker. Why reinvent the wheel, after all?

The above way is not that hard to implement, and it doesn't take too long, but generally requires me to remember too much syntax.

However, it is the preferable way to sort things in Java. Learning it helps a lot in sorting in general.

To modify what to sort, we simply modify the compareTo method:

public int compareTo( Object o ){
   B k = (B) o;
   if ( pages != k.pages ){
   return pages - k.pages;
   }
   else
   return title.compareTo( k.title );
}

as with method 1, if we wanted to sort descendingly:

public int compareTo( Object o ){
   B k = (B) o;
   if ( pages != k.pages ){
   return k.pages - pages;
   }
   else
   return title.compareTo( k.title );
}

or title first:

public int compareTo( Object o ){
   B k = (B) o;
   if ( title.compareTo( k.title ) != 0 )
   return title.compareTo( k.title );
   else
   return pages - k.pages;

or title descendingly:

public int compareTo( Object o ){
   B k = (B) o;
   if ( title.compareTo( k.title ) != 0 )
   return -1 * title.compareTo( k.title );
   else
   return pages - k.pages;

Method 3
So is there another alternative?

This requires us to think about the boundry conditions. Since Arrays.sort also sort Strings, we can format the entire thing as an Array of Strings, and then sort them:

import java.util.*;
public class Book{
   public String bookOrder( String books, int number ){
   StringTokenizer st = new StringTokenizer( books );
   String[] book = new String[ number ];

   // Parsing
   for ( int i = 0; i < number; i++ ){
       int pages = Integer.parseInt( st.nextToken() );
       String title = st.nextToken();

        /** Format is as following:

         * DDDTTNNNNN
         * Where DDD is the number of pages
         * TT is the initials
         * and NNNNN is the original string
         **/

       book[i] = format( pages ) + title + pages + " " + title;
   }
  
   // Using Arrays.sort
   Arrays.sort( book );
  
   String s = "";
   for ( int i = 0; i < number; i++ ){
   // Why 5?  the first 5 characters are throw away letters to be sorted
       s += book[i].substring(5) + " ";
   }
   return s.trim();
   }

   // This pads the number of pages with zeros.
   String format ( int pages ){
   String temp = "0000000" + pages;
   // Why 3?  Since it only goes up to 999, we only need the last 3 digits.
   return temp.substring( temp.length() - 3 );
   }
}

The above works, is very short to write, and is pretty intuitive. In general, I recommend the second method, but usually I have to look up the syntax on an API, and the above saves me some time, and time is a very important constraint sometimes.

To modify what to sort, we simply modify the parsing line:

   book[i] = format( pages ) + title + pages + " " + title;

to descending pages:

   book[i] = format( 999 - pages ) + title + pages + " " + title;

to initials:

   book[i] = title + format( 999 - pages ) + pages + " " + title;

to descending initials:

   book[i] = (char) ('Z' - ( title.charAt(0) - 'A' )) + (char) ('Z' - ( title.charAt(1) - 'A' ) +
     format( 999 - pages ) + pages + " " + title;

To test the above methods, we just need to add the main method:

    public static void main( String[] args )
   {
   Book a = new Book();
   System.out.println( a.bookOrder( "15 AB 219 AE 518 SE 518 AB 17 CE", 5 ) );
   }

This was meant to be a quick tutorial to coders that already knows how to program, and to provide them alternative way of solving a problem quicker.
http://devhood.com/Tutorials/tutorial_details.aspx?tutorial_id=395

Sorting Objects

2009-11-30T11:26:00.000-08:00

For simplicity we've applied the sorting algorithms we've looked at thus far to a primitive data type: long. However, sorting routines will more likely be applied to objects than primitive types. Accordingly, we show a Java program in Listing 3.4, objectSort.java, that sorts an array of Person objects (last seen in the classDataArray.java program in Chapter 2).

Java Code for Sorting Objects

The algorithm used in our Java program is the insertion sort from the preceding section. The Person objects are sorted on lastName; this is the key field. The objectSort.java program is shown in Listing 3.4.

LISTING 3.4 The `objectSort.java` Program

// objectSort.java

// demonstrates sorting objects (uses insertion sort)

// to run this program: C>java ObjectSortApp

////////////////////////////////////////////////////////////////

class Person

{

private String lastName;

private String firstName;

private int age;

//-----------------------------------------------------------

public Person(String last, String first, int a)

 {                // constructor

 lastName = last;

 firstName = first;

 age = a;

 }

//-----------------------------------------------------------

public void displayPerson()

 {

 System.out.print("  Last name: " + lastName);

 System.out.print(", First name: " + firstName);

 System.out.println(", Age: " + age);

 }

//-----------------------------------------------------------

public String getLast()      // get last name

 { return lastName; }

} // end class Person

////////////////////////////////////////////////////////////////

class ArrayInOb

{

private Person[] a;        // ref to array a

private int nElems;        // number of data items

//--------------------------------------------------------------

public ArrayInOb(int max)     // constructor

 {

 a = new Person[max];        // create the array

 nElems = 0;            // no items yet

 }

//--------------------------------------------------------------

                 // put person into array

public void insert(String last, String first, int age)

 {

 a[nElems] = new Person(last, first, age);

 nElems++;             // increment size

 }

//--------------------------------------------------------------

public void display()       // displays array contents

 {

 for(int j=0; j0 &&        // until smaller one found,

      a[in-1].getLast().compareTo(temp.getLast())>0)

    {

    a[in] = a[in-1];     // shift item to the right

    --in;          // go left one position

    }

   a[in] = temp;        // insert marked item

   } // end for

 } // end insertionSort()

//--------------------------------------------------------------

} // end class ArrayInOb

////////////////////////////////////////////////////////////////

class ObjectSortApp

{

public static void main(String[] args)

 {

 int maxSize = 100;       // array size

 ArrayInOb arr;         // reference to array

 arr = new ArrayInOb(maxSize); // create the array



 arr.insert("Evans", "Patty", 24);

 arr.insert("Smith", "Doc", 59);

 arr.insert("Smith", "Lorraine", 37);

 arr.insert("Smith", "Paul", 37);

 arr.insert("Yee", "Tom", 43);

 arr.insert("Hashimoto", "Sato", 21);

 arr.insert("Stimson", "Henry", 29);

 arr.insert("Velasquez", "Jose", 72);

 arr.insert("Vang", "Minh", 22);

 arr.insert("Creswell", "Lucinda", 18);



 System.out.println("Before sorting:");

 arr.display();         // display items



 arr.insertionSort();      // insertion-sort them



 System.out.println("After sorting:");

 arr.display();         // display them again

 } // end main()

} // end class ObjectSortApp

////////////////////////////////////////////////////////////////

Here's the output of this program:

Before sorting:

Last name: Evans, First name: Patty, Age: 24

Last name: Smith, First name: Doc, Age: 59

Last name: Smith, First name: Lorraine, Age: 37

Last name: Smith, First name: Paul, Age: 37

Last name: Yee, First name: Tom, Age: 43

Last name: Hashimoto, First name: Sato, Age: 21

Last name: Stimson, First name: Henry, Age: 29

Last name: Velasquez, First name: Jose, Age: 72

Last name: Vang, First name: Minh, Age: 22

Last name: Creswell, First name: Lucinda, Age: 18



After sorting:

Last name: Creswell, First name: Lucinda, Age: 18

Last name: Evans, First name: Patty, Age: 24

Last name: Hashimoto, First name: Sato, Age: 21

Last name: Smith, First name: Doc, Age: 59

Last name: Smith, First name: Lorraine, Age: 37

Last name: Smith, First name: Paul, Age: 37

Last name: Stimson, First name: Henry, Age: 29

Last name: Vang, First name: Minh, Age: 22

Last name: Velasquez, First name: Jose, Age: 72

Last name: Yee, First name: Tom, Age: 43

Lexicographical Comparisons

The insertSort() method in objectSort.java is similar to that in insertSort.java, but it has been adapted to compare the lastName key values of records rather than the value of a primitive type.

We use the compareTo() method of the String class to perform the comparisons in the insertSort() method. Here's the expression that uses it:

a[in-1].getLast().compareTo(temp.getLast()) > 0

The compareTo() method returns different integer values depending on the lexicographical (that is, alphabetical) ordering of the String for which it's invoked and the String passed to it as an argument, as shown in Table 3.1.

TABLE 3.1 Operation of the `compareTo()` Method

`s2.compareTo(s1)`	Return Value
`s1` < `s2`	<>
`s1` equals `s2`	0
`s1` > `s2`	> 0

For example, if s1 is "cat" and s2 is "dog", the function will return a number less than 0. In the objectSort.java program, this method is used to compare the last name of a[in-1] with the last name of temp.

Stability

Sometimes it matters what happens to data items that have equal keys. For example, you may have employee data arranged alphabetically by last names. (That is, the last names were used as key values in the sort.) Now you want to sort the data by ZIP code, but you want all the items with the same ZIP code to continue to be sorted by last names. You want the algorithm to sort only what needs to be sorted, and leave everything else in its original order. Some sorting algorithms retain this secondary ordering; they're said to be stable.

All the algorithms in this chapter are stable. For example, notice the output of the objectSort.java program (Listing 3.4). Three persons have the last name of Smith. Initially, the order is Doc Smith, Lorraine Smith, and Paul Smith. After the sort, this ordering is preserved, despite the fact that the various Smith objects have been moved to new locations.

2009-11-25T00:12:00.000-08:00

Sorting maps in Java based on it’s values
By paaloliver
Ever needed to sort a Map type collection in Java ?
Well i had to the other day and of course all the documentation pointed me in the direction of the SortedMap interface.
However, this datastructure is sorted on its keys and not on its values, which was really what I wanted to accomplish, so how do you do that? After a bit of fiddeling I found something that worked. Maybe its useful to you:public class MapValueSort {
/** inner class to do soring of the map **/
private static class ValueComparer implements Comparator {
private Map _data = null;
public ValueComparer (Map data){
super();
_data = data;
}
public int compare(Object o1, Object o2) {
String e1 = (String) _data.get(o1);
String e2 = (String) _data.get(o2);
return e1.compareTo(e2);
}
}
public static void main(String[] args){
Map unsortedData = new HashMap();
unsortedData.put("2", "DEF");
unsortedData.put("1", "ABC");
unsortedData.put("4", "ZXY");
unsortedData.put("3", "BCD");
SortedMap sortedData = new TreeMap(new MapValueSort.ValueComparer(unsortedData));
printMap(unsortedData);
sortedData.putAll(unsortedData);
System.out.println();
printMap(sortedData);
}
private static void printMap(Map data) {
for (Iterator iter = data.keySet().iterator(); iter.hasNext();) {
String key = (String) iter.next();
System.out.println("Value/key:"+data.get(key)+"/"+key);
}
}
}
This should output something of the lines of:Value/key:BCD/3
Value/key:DEF/2
Value/key:ZXY/4
Value/key:ABC/1
Value/key:ABC/1
Value/key:BCD/3
Value/key:DEF/2
Value/key:ZXY/4
Where the bottom last four lines obviously is sorted on the map’s values and not it’s keys.

2009-11-25T00:09:00.000-08:00

In this program you will learn how to sort words in a String. The sorting will be done in ascending order. We are going to use sort() method of String class in Java. The description of the code is given below for the usage of the method.

Description of the code:
Here, you will get to know about the sort() method through the following java program. In the program code given below, we have taken a String. First of all we will convert that string in array of characters. For this we have used toCharArray(); method. After that we have used sort(); method to sort that array of characters.

The code of the program is given below:

import java.util.*;

import java.io.*;

import java.lang.String;

public class SortWords{

public static void main(String args[]){

String str = "This is my new string";

char[] content = str.toCharArray();

java.util.Arrays.sort(content);

String sorted = new String(content);

System.out.println(content);

}

}
Output of the program:

C:\unique>javc SortWords

C:\unique>java SortWordsTeghiiimnnrssstwy

C:\unique>

Download this example.

Sorting a List

2009-11-25T00:08:00.000-08:00

Sorting a List // Create a list
String[] strArray = new String[] {"z", "a", "C"};
List list = Arrays.asList(strArray);

// Sort
Collections.sort(list);
// C, a, z

// Case-insensitive sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
// a, C, z

// Reverse-order sort
Collections.sort(list, Collections.reverseOrder());
// z, a, C

// Case-insensitive reverse-order sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
Collections.reverse(list);
// z, C, a

Sorting Arrays

2009-11-24T12:14:00.000-08:00

Sorting Arrays

Why you shouldn't write your own sort

Good student problem. A favorite computer science topic it sorting, putting a collection of data in some order. Typically this is done for arrays. Textbooks cover both the slow, O(n²), sorts (eg, selection, insertion, and bubble sorts) and fast, O(n log n), sorts (quick sort, heap sort, etc). These are interesting problems, give students a lot of practice with arrays, bring up important tradeoffs, and are generally quite educational.

Bad professional pratice. However, the Java library already has sort methods that are more efficient, more general, and more correct than anything you are likely to write yourself. And they are already written. Professional programmers use one of the java.util.Arrays.sort() methods; they do not write their own, except perhaps in unusual cases.

Other data structures. There are sort methods in the java.util.Collections class which can be used to sort other kinds of data structures (eg, ArrayList), and there are data structures such as TreeMap that keep elements sorted based on a key.

Sorting Arrays with `Arrays.sort(...)`

The java.util.Arrays class has static methods for sorting arrays, both arrays of primitive types and object types. The sort method can be applied to entire arrays, or only a particular range. For object types you can supply a comparator to define how the sort should be performed.

Method	Description
Arrays sort methods
`Arrays.sort(pa);`	Sorts the elements of the array of a primitive type into ascending order using their natural ordering.
`Arrays.sort(pa, from, to);`	Sorts the elements pa[from]...pa[to-1] of a primitive type. into ascending order.
`Arrays.sort(oa);`	Sorts the elements of the array of an object type into ascending order, using the order defined by `Comparable` interface, which defines the `compareTo` method. Note that many Java classes such as `String` (but not `StringBuffer`), `Double`, `BigInteger`, etc implement `Comparable`.
`Arrays.sort(oa, from, to);`	Sorts the elements of the array, in the range from...to of an object type into ascending order.
`Arrays.sort(oa, comp);`	Sorts the elements of the array of an object type into ascending order, using the Comparator comp.
`Arrays.sort(oa, from, to, comp);`	Sorts the elements of the array, in the range from...to of an object type into ascending order using the Comparator comp.

Example - Sorting arrays using Arrays.sort()

This example sorts an array of Strings and an array of doubles. All object types that implement Comparable (ie, defines compareTo() method), can be sorted with using a comparator. The Arrays.sort() method is also defined for primitive arrays.

// File   : data-arrays/dblsort/Dblsrt.java
// Purpose: To show how Arrays.sort() works with arrays
//          of both primitive and object values.
// Author : Fred Swartz 2006-08-23.  Public domain.

import java.util.Arrays;

public class Dblsrt {
   //========================================================= main
   public static void main(String[] args) {
       //... 1. Sort strings - or any other Comparable objects.
       String[] names = {"Zoe", "Alison", "David"};
       Arrays.sort(names);
       System.out.println(Arrays.toString(names));

       //... 2. Sort doubles or other primitives.
       double[] lengths = {120.0, 0.5, 0.0, 999.0, 77.3};
       Arrays.sort(lengths);
       System.out.println(Arrays.toString(lengths));
   }
}

Output from above program

[Alison, David, Zoe]
[0.0, 0.5, 77.3, 120.0, 999.0]

Selection Sort

2009-11-24T12:12:00.000-08:00

Selection Sort

NOTE: You should never write your own sort. Use the java.util.Arrays.sort(...) or java.util.Collections.sort(...).

Two nested loops. Like all simple sorts, selection sort is implemented with two nested loops.

Simple selection sort

The basic idea is to look at each element in the array, and for each element look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.

public static void selectionSort1(int[] x) {

   for (int i=0; i       for (int j=i+1; j           if (x[i] > x[j]) {

               //... Exchange elements

               int temp = x[i];

               x[i] = x[j];

               x[j] = temp;

           }

       }

   }

}

More efficient selection sort - Move every value only once

This more efficient variation of selection sort remembers the index of the smallest element that it finds in each pass. At the end of each pass it makes one exchange, if necessary. This is more efficient, but you shouldn't be writing your own sort - use java.util.Arrays.sort(...)!

public static void selectionSort2(int[] x) {

   for (int i=0; i       int minIndex = i;      // Index of smallest remaining value.

       for (int j=i+1; j           if (x[minIndex] > x[j]) {

               minIndex = j;  // Remember index of new minimum

           }

       }

       if (minIndex != i) {

           //...  Exchange current element with smallest remaining.

           int temp = x[i];

           x[i] = x[minIndex];

           x[minIndex] = temp;

       }

   }

}

http://www.leepoint.net/notes-java/data/arrays/31arrayselectionsort.html

Bubble sort

2009-11-24T12:03:00.000-08:00

Bubble Sorts

People like bubble sorts -- could it be the name? One nice aspect of bubble sorts is that they can quit early if the elements are almost sorted.

NOTE: As always, it's better if you don't write your own sorts. Java has better sort methods in java.util.Arrays.sort(...) and java.util.Collections.sort(...). But sorts are excellent practice, and are a technique that all students are expected to understand to some extent.

Bubble Sort -- fixed number of passes

This version of bubble sort makes a fixed number of passes (length of the array - 1). Each inner loop is one shorter than the previous one.

public static void bubbleSort1(int[] x) {

   int n = x.length;

   for (int pass=1; pass < n; pass++) {  // count how many times

       // This next loop becomes shorter and shorter

       for (int i=0; i < n-pass; i++) {

           if (x[i] > x[i+1]) {

               // exchange elements

               int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;

           }

       }

   }

}

Bubble Sort -- stop when no exchanges

This version of bubble sort continues making passes over the array as long as there were any exchanges. If the array is already sorted, this sort will stop after only one pass.

public static void bubbleSort2(int[] x) {

   boolean doMore = true;

   while (doMore) {

       doMore = false;  // assume this is last pass over array

       for (int i=0; i           if (x[i] > x[i+1]) {

              // exchange elements

              int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;

              doMore = true;  // after an exchange, must look again 

           }

       }

   }

}

Bubble Sort -- stop when no exchanges, shorter range each time

This version of bubble sort combines ideas from the previous versions. It stops when there are no more exchanges, and it also sorts a smaller range each time.

public static void bubbleSort3(int[] x) {

   int n = x.length;

   boolean doMore = true;

   while (doMore) {

       n--;

       doMore = false;  // assume this is our last pass over the array

       for (int i=0; i           if (x[i] > x[i+1]) {

               // exchange elements

               int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;

               doMore = true;  // after an exchange, must look again

           }

       }

   }

}//end method bubbleSort3

Bubble Sort -- Sort only necessary range

After a pass on bubble sort, it's only necessary to sort from just below the first exchange to just after the last exchange, because everything that wasn't exchanged must be in the correct order. This version of bubble sort remembers the lowest and highest locations where there was an exchange, and sorts only that part of the array. Although it is a little more complicated, it is more efficient than the other bubble sorts.

public static void bubbleSort4(int[] x) {

   int newLowest = 0;            // index of first comparison

   int newHighest = x.length-1;  // index of last comparison



   while (newLowest < newHighest) {

       int highest = newHighest;

       int lowest  = newLowest;

       newLowest = x.length;    // start higher than any legal index

       for (int i=lowest; i           if (x[i] > x[i+1]) {

              // exchange elements

              int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;

              if (i                  newLowest = i-1;

                  if (newLowest < 0) {

                      newLowest = 0;

                  }

              } else if (i>newHighest) {

                  newHighest = i+1;

              }

           }

       }

   }

}//end method bubbleSort4



http://www.leepoint.net/notes-java/data/arrays/32arraybubblesort.html

Arrays.sort()

2009-11-24T12:02:00.001-08:00

Example - Sorting arrays using Arrays.sort()

// File   : data-arrays/dblsort/Dblsrt.java
// Purpose: To show how Arrays.sort() works with arrays
//          of both primitive and object values.
// Author : Fred Swartz 2006-08-23.  Public domain.

import java.util.Arrays;

public class Dblsrt {
   //========================================================= main
   public static void main(String[] args) {
       //... 1. Sort strings - or any other Comparable objects.
       String[] names = {"Zoe", "Alison", "David"};
       Arrays.sort(names);
       System.out.println(Arrays.toString(names));

       //... 2. Sort doubles or other primitives.
       double[] lengths = {120.0, 0.5, 0.0, 999.0, 77.3};
       Arrays.sort(lengths);
       System.out.println(Arrays.toString(lengths));
   }
}

Output from above program

[Alison, David, Zoe]
[0.0, 0.5, 77.3, 120.0, 999.0]

Sorting Algorithms

2009-11-23T04:57:00.000-08:00

Sorting Algorithms

We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorithms while sorting an array of data using in-place algorithms. This means that the algorithms do not allocate additional storage to hold temporary results: they sort the data in place.

Some of these sorts are very stupid or very slow and should not be used in code. The use of Bubblesort is deprecated. So don't use Bubblesort! Also, don't use Swapsort! It is only a demonstration of the amount of time Java takes to swap n elements.

In-Place Mergesort is yet another abomination. Mergesort is supposed to run in O(n log n), but the implementation here runs in O(n * n). This is because a temporary scratch array is not used. As with most of the examples here, In-Place Mergesort sorts the elements in the array without using additional storage (other than the stack used for the recursive calls, and temporary variables). Jack Snoeyink has provided me with a the Double Storage mergesort algorithm sort implementation that uses a scratch array.

New: Radix sort by Alvin Raj, August 13, 2002.

Bubble Sort (by James Gosling and Jason Harrison)
Bi-Directional Bubble Sort (by James Gosling)
Selection Sort (by Jason Harrison)
Shaker Sort (by Jason Harrison)
Insertion Sort (by Jason Harrison)
In-Place Merge Sort (by Jason Harrison)
Double Storage Merge Sort (by Jack Snoeyink)
Comb Sort 11 (by Jason Harrison)
Shell Sort (by Jason Harrison)
Heap Sort (by Jason Harrison)
Quick Sort (by James Gosling)
Quick Sort with Bubblesort (by Jim Boritz)
Enhanced Quick Sort (by Jim Boritz)
Fast Quick Sort (by Denis Ahrens)
Radix Sort Algorithm (by Alvin Raj) LinkedQueue.java and intNode.java

Java Sorting

Selection Sort Algorithm in Java

Recursion

Towers of Hanoi

Tail Recursion

Merge Sort Implementation in Java

Binary search

Binary Trees

Java Binary Trees and Solutions

Java Binary Tree Structure

OOP Style vs. Recursive Style

Java Solutions

1. Build123() Solution (Java)

2. size() Solution (Java)

3. maxDepth() Solution (Java)

4. minValue() Solution (Java)

5. printTree() Solution (Java)

6. printPostorder() Solution (Java)

7. hasPathSum() Solution (Java)

8. printPaths() Solution (Java)

9. mirror() Solution (Java)

10. doubleTree() Solution (Java)

11. sameTree() Solution (Java)

12. countTrees() Solution (Java)

13. isBST1() Solution (Java)

14. isBST2() Solution (Java)

Java, sorting, ArrayList example, generics

partitioning sorting code

shell sorting code

insertion code

selection sort code

bubble sort code

Collections methods

Some useful Collections methods

Searching may also be implemented in data structure classes

Sorting may be implicit in a data structure class

Array Library Methods

Use java.util.Arrays.toString(...) for debugging

Use Arrays.asList(...) for Collections view of array

Shuffling (randomizing) an array

Searching and Sorting Overview

Why searching and sorting are often treated together

Comparing 3 ways - Operators, Comparable, Comparator

Use predefined sorting and searching methods if possible.

Predefined sorting and searching methods for arrays

Predefined sorting and searching in the Collections classes

Algorithms: Recursive Binary Search

Recursive Binary Search

Example

Algorithms: Linear Search

Look at every element

Performance

Example

Algorithms: Binary Search

Divide in half

Performance

Example

Computing the midpoint

Variation on binary search

Sorting Effectively in Java

Sorting Objects

Java Code for Sorting Objects

LISTING 3.4 The objectSort.java Program

Lexicographical Comparisons

TABLE 3.1 Operation of the compareTo() Method

Stability

Sorting a List

Sorting Arrays

Sorting Arrays

Why you shouldn't write your own sort

Sorting Arrays with Arrays.sort(...)

Example - Sorting arrays using Arrays.sort()

Output from above program

Selection Sort

Selection Sort

Simple selection sort

More efficient selection sort - Move every value only once

Bubble sort

Bubble Sorts

Bubble Sort -- fixed number of passes

Use `java.util.Arrays.toString(...)` for debugging

Use `Arrays.asList(...)` for Collections view of array

LISTING 3.4 The `objectSort.java` Program

TABLE 3.1 Operation of the `compareTo()` Method

Sorting Arrays with `Arrays.sort(...)`