Saturday, December 22, 2007

Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(n log n) comparisons to sort n items. However, in the worst case, it makes Θ(n^2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which are always sorted. The algorithm always terminates because it puts at least one element in its final place on each iteration.

Quicksort with median-of-three partitioning functions nearly the same as normal quicksort with the only difference being how the pivot item is selected. In normal quicksort the first element is automatically the pivot item. This causes normal quicksort to function very inefficiently when presented with an already sorted list. The divison will always end up producing one sub-array with no elements and one with all the elements (minus of course the pivot item). In quicksort with median-of-three partitioning the pivot item is selected as the median between the first element, the last element, and the middle element (decided using integer division of n/2). In the cases of already sorted lists this should take the middle element as the pivot thereby reducing the inefficency found in normal quicksort.

The following code shows how to implement quick aortwith median-of-three partitioning and cutoff for small arrays:

/**
* Quicksort algorithm.
* @param a an array of Comparable items.
*/
public static void quicksort( Comparable [ ] a ) {
quicksort( a, 0, a.length - 1 );
}

private static final int CUTOFF = 10;

/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* @param a an array of Comparable items.
* @param low the left-most index of the subarray.
* @param high the right-most index of the subarray.
*/
private static void quicksort( Comparable [ ] a, int low, int high ) {
if( low + CUTOFF > high )
insertionSort( a, low, high );
else {
// Sort low, middle, high
int middle = ( low + high ) / 2;
if( a[ middle ].compareTo( a[ low ] ) < 0 )
swapReferences( a, low, middle );
if( a[ high ].compareTo( a[ low ] ) < 0 )
swapReferences( a, low, high );
if( a[ high ].compareTo( a[ middle ] ) < 0 )
swapReferences( a, middle, high );

// Place pivot at position high - 1
swapReferences( a, middle, high - 1 );
Comparable pivot = a[ high - 1 ];

// Begin partitioning
int i, j;
for( i = low, j = high - 1; ; ) {
while( a[ ++i ].compareTo( pivot ) < 0 )
;
while( pivot.compareTo( a[ --j ] ) < 0 )
;
if( i >= j )
break;
swapReferences( a, i, j );
}

// Restore pivot
swapReferences( a, i, high - 1 );

quicksort( a, low, i - 1 ); // Sort small elements
quicksort( a, i + 1, high ); // Sort large elements
}
}

/**
* Method to swap to elements in an array.
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static final void swapReferences( Object [ ] a, int index1, int index2 ) {
Object tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}


/**
* Internal insertion sort routine for subarrays
* that is used by quicksort.
* @param a an array of Comparable items.
* @param low the left-most index of the subarray.
* @param n the number of items to sort.
*/
private static void insertionSort( Comparable [ ] a, int low, int high ) {
for( int p = low + 1; p <= high; p++ ) {
Comparable tmp = a[ p ];
int j;

for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
a[ j ] = a[ j - 1 ];
a[ j ] = tmp;
}
}

Saturday, December 15, 2007

Heap Sort Implementation in Java

Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.

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

/**
* Standard heapsort.
* @param a an array of Comparable items.
*/
public static void heapsort( Comparable [ ] a )
{
for( int i = a.length / 2; i >= 0; i-- ) /* buildHeap */
percDown( a, i, a.length );
for( int i = a.length - 1; i > 0; i-- )
{
swapReferences( a, 0, i ); /* deleteMax */
percDown( a, 0, i );
}
}

/**
* Internal method for heapsort.
* @param i the index of an item in the heap.
* @return the index of the left child.
*/
private static int leftChild( int i )
{
return 2 * i + 1;
}

/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* @param a an array of Comparable items.
* @index i the position from which to percolate down.
* @int n the logical size of the binary heap.
*/
private static void percDown( Comparable [ ] a, int i, int n )
{
int child;
Comparable tmp;

for( tmp = a[ i ]; leftChild( i ) < i =" child">)
{
child = leftChild( i );
if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )
child++;
if( tmp.compareTo( a[ child ] ) < 0 )
a[ i ] = a[ child ];
else
break;
}
a[ i ] = tmp;
}


/**
* Method to swap to elements in an array.
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static final void swapReferences( Object [ ] a, int index1, int index2 )
{
Object tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}

Saturday, December 08, 2007

Review: GlobalSat BT-359 Bluetooth GPS

By Melissa Oxendale
July 17, 2007

Click to View
I have never played with GPS before, but have used a Bluetooth headset with my BlackBerry and a Bluetooth mouse with my PC. That's all the experience I have with Bluetooth and GPS. So trying out the GlobalSat BT-359 Bluetooth GPS receiver, which combines the two technologies, was a unique experience.

My verdict: It successfully turned the BlackBerry I tested it with into a navigation and location-based services tool.

The unit I reviewed is the same as the one sold by AT&T. It came with a wall charger and car charger adapters, and charges via a USB cable just like a BlackBerry, which makes charging easy and the adapters very useful. My review unit came charged, which is always nice. There is nothing worse than waiting for a battery charge before playing with a new toy.

First, the GlobalSat BT-359 Bluetooth GPS Receiver was smaller than I expected, smaller than the BlackBerry Pearl even (see picture - Pearl on left, GlobalSat BT-359 on right).

It has a back door for battery replacement, 3 LED lights, and a power button. One light is the power indicator, letting you know if the battery is low and if the receiver is charging. Another light indicates if the receiver is locked into the GPS satellite network: If it flashes it is connected, if it is solid it is not. The last light is the Bluetooth indicator, a slow flash means it is not connected and a faster flash means it is.

Pairing the receiver with the Pearl was simple. I just went into the Bluetooth menu on the BlackBerry and added the device.

The receiver worked fine with RIM's BlackBerry Maps and Google Maps.

I liked the options available in Google Maps a little better. I tried it with Telenav and Nav4All navigation and tracking applications without any problems at all.

With the receiver, I was able to obtain a connection to the GPS satellites inside my apartment without any problem, as well as everywhere I drove around. When watching the location on the map while driving at interstate speeds the receiver and image on the maps was able to keep up no problem.

The battery is supposed to last for up to 11 hours, in continuous mode. The receiver powers itself down after 10 minutes of inactivity to save power.

In addition to AT&T, you can get the GlobalSat BT-359 Bluetooth GPS receiver through RIM's BlackBerry accessories Web site. It is available for a range of prices from various Web sites, for between $100 and $140.

Thursday, December 06, 2007

Review: Seidio Holster: The Best Available for the BlackBerry Curve

By Melissa Oxendale
July 31, 2007

Click to View
I recently tried out a new holster for the BlackBerry Curve from Seido. And, I have to say, it was simply one of the best I've ever used.

The first thing I noticed was a red sticker that says PDA Face In Design. This can be useful as I know a few people have tried to use various holsters with the face out, which turns out to be hard on a BlackBerry.

On the inside where the face of your Curve would be is a nice soft lining. No need to worry about it scratching up the face or screen.

The clip on the back swivels around so you can clip it on at whatever angle works best for you. I tried it on my belt, in my hip pocket, in my leg cargo pocket, and even clipped it to my purse. It worked great every way I could think of. The clip held fast to everything I attached it to regardless of the tugging and pulling I tried on it.

There is a spring loaded clip at the top to hold in your Curve. It works wonderfully. It does not require too much elbow grease to open it, but holds your Curve in flawlessly. I never once worried that my Curve was going to get loose.

One of the added benefits of this holster is it will fit an extended battery; once they become available for the Curve. So if you pick this Seido holster now, you won't have to worry about a new one down the road.

The Curve does not have to come out of the holster to charge. All the side buttons, including the USB port and headphone jack are available to use while secure in the holster.

The holster for the Curve sells for $29.95 and is available from Seidio's online store.

Tuesday, December 04, 2007

How to extract file/files from a zip file

.util.zip provides classes to extract, read and

write zip files.

Example below extracts files from given zip file into destination folder. import java.io.*;
import java.util.zip.*;

class testZipFiles
{
public static void main(String[] args)
{
if (args.length != 1)
{
System.out.println("Usage: java testFiles [zipfile path] ");
return;
}
try
{
String filename = args[0];
testZipFiles list = new testZipFiles( );
list.getZipFiles(filename);
}
catch (Exception e)
{
e.printStackTrace();
}
}

public void getZipFiles(String filename)
{
try
{
String destinationname = "d:\\servlet\\testZip\\";
byte[] buf = new byte[1024];
ZipInputStream zipinputstream = null;
ZipEntry zipentry;
zipinputstream = new ZipInputStream(
new FileInputStream(filename));

zipentry = zipinputstream.getNextEntry();
while (zipentry != null)
{
//for each entry to be extracted
String entryName = zipentry.getName();
System.out.println("entryname "+entryName);
int n;
FileOutputStream fileoutputstream;
File newFile = new File(entryName);
String directory = newFile.getParent();

if(directory == null)
{
if(newFile.isDirectory())
break;
}

fileoutputstream = new FileOutputStream(
destinationname+entryName);

while ((n = zipinputstream.read(buf, 0, 1024)) > -1)
fileoutputstream.write(buf, 0, n);

fileoutputstream.close();
zipinputstream.closeEntry();
zipentry = zipinputstream.getNextEntry();

}//while

zipinputstream.close();
}
catch (Exception e)
{
e.printStackTrace();
}
}
}

Saturday, December 01, 2007

How to show data in database with a JTable

This Java Swing tip illustrates a method of showing data in database in a JTable. JTable act as a output for the database. The developer may use this to display a part of data (for example data generated form a query) to the user in a table. The table gives user an impression of database.

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.table.*;

public class DatabaseTest extends JFrame {

JTextField hostField;
JTextField queryField;
QueryTableModel qtm;

public DatabaseTest() {
super("Database Test Frame");
setDefaultCloseOperation(EXIT_ON_CLOSE);
setSize(350, 200);

qtm = new QueryTableModel();
JTable table = new JTable(qtm);
JScrollPane scrollpane = new JScrollPane(table);
JPanel p1 = new JPanel();
p1.setLayout(new GridLayout(3, 2));
p1.add(new JLabel("Enter the Host URL: "));
p1.add(hostField = new JTextField());
p1.add(new JLabel("Enter your query: "));
p1.add(queryField = new JTextField());
p1.add(new JLabel("Click here to send: "));

JButton jb = new JButton("Search");
jb.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
qtm.setHostURL(hostField.getText().trim());
qtm.setQuery(queryField.getText().trim());
}
} );
p1.add(jb);
getContentPane().add(p1, BorderLayout.NORTH);
getContentPane().add(scrollpane, BorderLayout.CENTER);
}

public static void main(String args[]) {
DatabaseTest tt = new DatabaseTest();
tt.setVisible(true);
}
}

Monday, November 19, 2007

How to create a Linked List

This Java tip illustrates a method of creating a List. The tip here describes various aspects of linked list such as adding an element in a list, retrieving an element and removing an element from the list.

// Create a link list
List list = new LinkedList(); // Doubly-linked list
list = new ArrayList(); // List implemented as growable array

// Append an element to the list
list.add("a");

// Insert an element at the head (0) of the list
list.add(0, "b");

// Get the number of elements in the list
int size = list.size(); // 2

// Retrieving the element at the end of the list
Object element = list.get(list.size()-1); // a

// Retrieving the element at the head of the list
element = list.get(0); // b

// Deleting occurrance of the first element of the link list
boolean b = list.remove("b"); // true
b = list.remove("b"); // false

// Remove the element at a particular index
element = list.remove(0); // a

Thursday, November 15, 2007

Review: Jazzing Up the BlackBerry Curve with a Case and Stickers

By Melissa Oxendale
December 7, 2007

While I still love my Fortte case (see our review), I wanted to try something a little different for my BlackBerry. I wanted something to make my Curve stand out. So off to eBay I went.

I found stickers to personalize my BlackBerry that you could pick in a large number of designs for around $8. Many were colorful and abstract, while some sported sunsets and scenic views. All the choices made it hard to pick three I wanted.

To compliment my new stickers, I decided to get a hard clear case to go over them. So I ended up ordering the Super Slim Crystal Hard Case from Seidio.

It took about week for everything to arrive.

First, I started with a screen protector, as Seidio's Crystal case does not cover the screen. (All the pictures in this story are of the Curve with the screen protector, case and stickers installed.

Stickers
Once the screen was covered I moved to the stickers. The hardest part was pulling the front off the paper. It had the buttons cut out, but the sticker material was still there. I was sure putting the sticker over my buttons would be a painful experience. I even started with my least favorite sticker, just in case I ruined it.

Turns out my concerns weren't founded. For the most part, the sticker easily fell into place, although I had a little trouble getting it placed correctly at the top as I seemed to always put it a little too far to the left.

One word of caution: if the sticker goes over the screen protector, it will pull the screen protector up when you tug on it.

The back of the sticker pack had two pieces. On piece went over the back cover, so you are able to take it off to reach the battery, SIM, and memory card. The other went around the door. The back door part had cut outs for the camera, flash, and mirror. I had no trouble at all putting the back door sticker on. With the smaller part that stuck directly to the phone, I again wanted to put it a little too far to the left.

Overall, the stickers applied much easier than I expected. And there weren't any problems with air bubbles underneath it. They're a cheap and easy way personalize your BlackBerry.

Seido Crystal Case
On top of the sticker went my new Seidio Crystal Case.

It came with simple to follow instructions that guide you to getting the case on. I could tell right away it wasn't snapped all the way on because it made the side keys hard to type on. Just a little extra squeeze and it snapped into place.

All of the buttons, headphone jack, and USB jack were easy to get to. With the Crystal Case on the Curve was too large for my Fortte case or the pouch it came with, however. I was able to fit it into a case I used with my 8700 though, even through it was not designed with a trackball in mind. It also fit in the BlackBerry case that came with the AT&T 8820. I would imagine it would fit in most cases that have the elastic on the sides.

Now my BlackBerry will stand out, although I no longer have anywhere to attach my Tardis Phone Charm. Even with stickers and new case, typing was still a breeze.

The Seidio Crystal case is $24.95 at Seidio's Web site. The stickers were around $8.00 for three on eBay.

Friday, November 09, 2007

How to create a bouncing ball

This Java tip shows how to create a bouncing ball animation using threads.


Image

import java.awt.Container;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class BounceThread {
public static void main(String[] args) {
JFrame frame = new BounceThreadFrame();
frame.show();
}
}

class BounceThreadFrame extends JFrame {
public BounceThreadFrame() {
setSize(300, 200);
setTitle("Bounce");

addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});

Container contentPane = getContentPane();
canvas = new JPanel();
contentPane.add(canvas, "Center");
JPanel p = new JPanel();
addButton(p, "Start", new ActionListener() {
public void actionPerformed(ActionEvent evt) {
Ball b = new Ball(canvas);
b.start();
}
});

addButton(p, "Close", new ActionListener() {
public void actionPerformed(ActionEvent evt) {
canvas.setVisible(false);
System.exit(0);
}
});
contentPane.add(p, "South");
}

public void addButton(Container c, String title, ActionListener a) {
JButton b = new JButton(title);
c.add(b);
b.addActionListener(a);
}

private JPanel canvas;
}

class Ball extends Thread {
public Ball(JPanel b) {
box = b;
}

public void draw() {
Graphics g = box.getGraphics();
g.fillOval(x, y, XSIZE, YSIZE);
g.dispose();
}

public void move() {
if (!box.isVisible())
return;
Graphics g = box.getGraphics();
g.setXORMode(box.getBackground());
g.fillOval(x, y, XSIZE, YSIZE);
x += dx;
y += dy;
Dimension d = box.getSize();
if (x < 0) {
x = 0;
dx = -dx;
}
if (x + XSIZE >= d.width) {
x = d.width - XSIZE;
dx = -dx;
}
if (y < 0) {
y = 0;
dy = -dy;
}
if (y + YSIZE >= d.height) {
y = d.height - YSIZE;
dy = -dy;
}
g.fillOval(x, y, XSIZE, YSIZE);
g.dispose();
}

public void run() {
try {
draw();
for (int i = 1; i <= 1000; i++) {
move();
sleep(5);
}
} catch (InterruptedException e) {
}
}

private JPanel box;

private static final int XSIZE = 10;

private static final int YSIZE = 10;

private int x = 0;

private int y = 0;

private int dx = 2;

private int dy = 2;
}

Monday, November 05, 2007

Verizon Picks Up Smartphone Trio

By James Alan Miller
March 31, 2008

Click to View
Verizon Wireless expanded its already substantive portfolio of smartphones today, announcing plans to soon carry the BlackBerry Curve, HTC Touch, and the Motorola Q9. America's second largest wireless carrier made these announcements as the technology world focuses its gaze on Las Vegas, where the giant spring edition of the CTIA Wireless trade show and conference gears up to get started tomorrow.

Like AT&T's BlackBerry Curve, Verizon's version, called the BlackBerry 8330, integrates GPS to support location-based services, such as the operator's own VZ Navigator mapping service. It also sports a QWERTY thumb-keyboard, a 2 megapixel camera, QVGA screen, and Bluetooth 2.0. High-capacity SDHC memory cards and Verizon's 3G cellular-wireless data network are also supported.

Due in May, Verizon plans to sell the BlackBerry for $270 with a two-year agreement and after a $50 mail-in rebate. When you sign up for a qualifying voice and data plan the price drops $100 further.

The Motorola Q9c is essentially the same as the Q9m Verizon launched last summer, QWERTY keyboard and all. It integrates GPS, supports EV-DO and runs on Windows Mobile 6 Standard, which means the new Q, like all other Qs, doesn't have a touch screen.

The Q9c’s software bundle directs it more toward the business user than the earlier Q model, which placed more of a premium on multimedia. It is colored a bright a cheery lime-green, however.

When the Q9c ships next month, expect it to go for $250 with a two-year agreement and after a rebate. In addition to Verizon, Alltel and U.S. Cellular just picked up the Q9c as well.

Already available from Sprint and Alltel, Verizon is the third carrier-home HTC has found for the Touch in the U.S. Verizon is not calling it by that name, however, preferring the moniker XV6900 instead. And, unlike the other carriers, Verizon has chosen to enable the Touch’s GPS receiver to support its VZ Navigator service.

Otherwise, the Windows Mobile 6-run XV6900 seems to be nearly identical to the other Touches, with its 2 megapixel camera and similar - if not exactly the same – specifications.

As with the iPhone, the chief means of interaction between a Touch and a user is through the smartphone's touch screen and the user's fingers through HTC's proprietary TouchFLO technology, which essentially grafts an advanced touch interface onto the Windows Mobile user interface.

Due in April, Verizon expects to sell the XV6900 for $350 after a $50 mail-in rebate and if you sign up for two years—par for the course these days, it seems.

Although Apple sold twice as many iPhones, hitting the 4 million mark, last year, HTC moved a couple million Touches, not a shabby number by any means.

Monday, October 29, 2007

An example of Regular Expression search and replace program

This Java tip illustrates an example of Quintessential Regular Expression search and replace program. This program finds all matches to a regular expression pattern and replaces them with another string.

import java.util.regex.*;

public class BasicReplace {

public static void main(String[] args) {

CharSequence inputStr = "p q r p q r ";
String patternStr = "q";
String replacementStr = "s";

// Compile regular expression
Pattern pattern = Pattern.compile(patternStr);

// Replace all occurrences of pattern in input
Matcher matcher = pattern.matcher(inputStr);
String output = matcher.replaceAll(replacementStr);
// p s r p s r
}
}