A working QuickFind Java source file for the Sedgewick Algorithms book.

I’m posting this code because of my frustration in dealing with the code for the QuickFind algorithm in the book “Algorithms” on page 221. Sedgewick or Wayne, whomever wrote this code, hides a Scanner System.in read in their so called “StdIn.readInt()” library. In other words, when you run their version of QuickFind by typing in: “java QuickFind tinyUF.txt”, as it tells you to in the book, in the command line to run the program, absolutely NOTHING happens because the program is waiting for YOU to type in each and every single int value in the tinyUF.txt file and then hit enter for each value!

Now this might not be such a huge problem when your only dealing with 11 connections, since you “only” have to type in 23 values, by hand, and also hit enter 23 times for each value but it would be an absolutely ridiculous task to try and type in all of the connections for the mediumUF or largeUF files as the former has 900 connections and the latter has 2,000,000 connections. You would spend the rest of your natural life typing in the values on these files just to run a simple QuickFind algorithm.

The code I’ve posted below makes the program read in the values from the file automatically, so that you don’t have to type them in manually.

import java.io.File;
import java.util.Scanner;

public class QuickFind {
private int[] id; //access to component id (site indexed)
private int count; //number of components
private int N;

public QuickFind(int N){ //initialize component id array
this.N = N;
count = N;
id = new int[N];

System.out.print(“Current array status: “);
for (int i = 0; i < N; i++){
id[i] = i;
System.out.print(id[i]);
}
System.out.println(“”);
}//end QuickFind() constructor

public int count(){
return count;
}//end count()

public boolean connected(int p, int q){
return ( find(p) == find(q) );//are p & q in the same group
}//end connected()

public int find(int p){
return id[p];
}//end find()

public void union(int p, int q){//put p and q into the same component
int pID = find(p);
int qID = find(q);
//do nothing is p and q are already in the same group
if (pID == qID) return;

//rename p’s component (group) to q’s name.
for (int i = 0; i < id.length; i++){
if (id[i] == pID) id[i] = qID;
}
System.out.println(p + ” and ” + q + ” are now connected”);
System.out.print(“Current array status: “);
for (int i = 0; i < N; i++){
System.out.print(id[i]);
}
System.out.println(“”);
count–;
}//end union()

public static void main(String[] args) {
Scanner scan = null;
try{
scan = new Scanner(new File( //use forward slashes next
“C:/…wherever you saved the tinyUF file…/tinyUF.txt”));
} catch (Exception ex){
System.out.println(“Could not find file”);
}
//solve dynamic connectivity problem
int N = scan.nextInt();// read number of sites.
System.out.println(“Array length is: ” + N);

QuickFind uf = new QuickFind(N);
while (scan.hasNext()){
int p = scan.nextInt();
int q = scan.nextInt(); //read pair to connect
if (uf.connected(p, q)){
System.out.println(p + ” and ” + q + ” are already connected”);
continue; //ignore if connected
}
uf.union(p, q); //combine components

}
StdOut.println(uf.count() + ” components”);
scan.close();

}//end main()
}

______|||||END PROGRAM||||||_______

This is the output you should get:

Array length is: 10
Current array status: 0123456789
4 and 3 are now connected
Current array status: 0123356789
3 and 8 are now connected
Current array status: 0128856789
6 and 5 are now connected
Current array status: 0128855789
9 and 4 are now connected
Current array status: 0128855788
2 and 1 are now connected
Current array status: 0118855788
8 and 9 are already connected
5 and 0 are now connected
Current array status: 0118800788
7 and 2 are now connected
Current array status: 0118800188
6 and 1 are now connected
Current array status: 1118811188
1 and 0 are already connected
6 and 7 are already connected
2 components

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s