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.

Read more »

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

Read more »

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:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists
3. 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 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

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

Read more »

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

}


Read more »

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