Add new code

Signed-off-by: Carlos Maiolino <[email protected]>

4 files changed, 153 insertions, 0 deletions

diff --git a/java/qfind/QuickFindUF.java b/java/qfind/QuickFindUF.java
new file mode 100644
index 0000000..4018515
--- /dev/null
+++ b/java/qfind/QuickFindUF.java
@@ -0,0 +1,39 @@
+/*
+ * Quick Find algorithm
+ *
+ * Very slow as it uses N^2 time as it needs to access the whole array twice.
+ *
+ * If we have a 10^9 union commands on 10^9 objects, we'll need 10^18 operations
+ * to actually finish the algorithm.
+ * 30+ years of computer time.
+ *
+ * Quadratic algorithms don't scale with technology.
+ */
+
+public class QuickFindUF {
+	private int[] id;
+
+	/* Constructor */
+	public QuickFindUF(int N) {
+		id = new int[N];
+
+		for (int i = 0; i < N; i++)
+			id[i] = i;
+	}
+
+	/* Are the objects connected */
+	public boolean connected(int p, int q) {
+		return id[p] == id[q];
+	}
+
+	/* Connect two objects */
+	public void union(int p, int q) {
+		int pid = id[p];
+		int qid = id[q];
+
+		for (int i = 0; i < id.length; i++) {
+			if (id[i] == pid)
+				id[i] = qid;
+		}
+	}
+}
diff --git a/java/qfind/QuickUnionUF.java b/java/qfind/QuickUnionUF.java
new file mode 100644
index 0000000..aab4fb4
--- /dev/null
+++ b/java/qfind/QuickUnionUF.java
@@ -0,0 +1,47 @@
+/*
+ * Quick Union algorithm
+ *
+ * Slightly better than quickfind
+ *
+ * treats each element in the array as a node in a tree and trees may be
+ * connected together or not. Essentially each element might be its own tree.
+ *
+ * Find: Check if p and q have the same root
+ *
+ * Union. Merge components containing p and q, set the id of p's root to the id
+ * of q's root.
+ *
+ * Still too slow though. Trees can get too tall, where the worst case is a tree
+ * where one element points to a single one until the end of the tree,
+ * essentially creating an array.
+ */
+
+public class QuickUnionUF {
+	private int[] id;
+
+	/* Constructor */
+	public QuickUnionUF(int N) {
+		id = new int[N];
+
+		for (int i = 0; i < N; i++)
+			id[i] = i;
+	}
+
+	/* Return root of 'i' */
+	private int root(int i) {
+		while (i != id[i])
+			i = id[i];
+		return i;
+	}
+
+	/* Are the objects connected */
+	public boolean connected(int p, int q) {
+		return root(p) == root(q);
+	}
+
+	/* Connect two objects */
+	public void union(int p, int q) {
+		int proot = root(p);
+		id[proot] = root(q);
+	}
+}
diff --git a/java/qfind/WeightedQuickUnionUF.java b/java/qfind/WeightedQuickUnionUF.java
new file mode 100644
index 0000000..45f8ba7
--- /dev/null
+++ b/java/qfind/WeightedQuickUnionUF.java
@@ -0,0 +1,62 @@
+/*
+ * Weighted Quick Union algorithm
+ *
+ * Adds weight to the quick union.
+ *
+ * Find: Check if p and q have the same root
+ *
+ * Union. Merge trees, but the merge is done depending on the size of each tree.
+ * The smaller one will be merged into the larger one.
+ *
+ * The downside is we need to keep a new extra array to keep track of the
+ * number of elements on each node.
+ *
+ */
+
+public class WeightedQuickUnionUF {
+	private int[] id;
+	private int[] sz;
+
+	/* Constructor */
+	public WeightedQuickUnionUF(int N) {
+		id = new int[N];
+		sz = new int[N];
+
+		for (int i = 0; i < N; i++)
+			id[i] = i;
+
+		/* Every node starts with a single item, itself */
+		for (int i = 0; i < N; i++)
+			sz[i] = 1;
+	}
+
+	/* Return root of 'i' */
+	private int root(int i) {
+		while (i != id[i]) {
+			/* Compress paths, by pointing the current node to the
+			 * root of its parent */
+			id[i] = id[id[i]];
+			i = id[i];
+		}
+		return i;
+	}
+
+	/* Are the objects connected */
+	public boolean connected(int p, int q) {
+		return root(p) == root(q);
+	}
+
+	/* Connect two objects */
+	public void union(int p, int q) {
+		int proot = root(p);
+		int qroot = root(q);
+
+		if (sz[proot] < sz[qroot]) {
+			id[proot] = qroot;
+			sz[proot] += sz[qroot];
+		} else {
+			id[qroot] = proot;
+			sz[qroot] += sz[proot];
+		}
+	}
+}
diff --git a/java/qfind/qfind.java b/java/qfind/qfind.java
new file mode 100644
index 0000000..eb274c0
--- /dev/null
+++ b/java/qfind/qfind.java
@@ -0,0 +1,5 @@
+public class qfind {
+	public static void main(String args[]) {
+		System.out.println("Hello World");
+	}
+}