Weighted Quick Union with Path Compression [Union Find] [Dynamic Connectivity][Java][Implementation]

This implementations has weights associated with each node of the trees in the forest. Smaller weights are added to larger ones (smaller trees merged with larger). Path compression keeps tree completely flat.

Depth of any node x is at most lg N.

Worst case time of Weighted QuickUnion + Path compression : N + M lg* N

[lg* N  =  iterated log function]

The iterated logarithm of n, written log* n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition is the result of this recursive function:

Code:

import java.util.Arrays; 

public class QuickUnionUF {

    private int[] id;
    private int[] sz;

    public QuickUnionUF(int N) {
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; ++i) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    private int root(int i) {  
        /*
        With Path Compression - Path compression keeps the tree completely flat!
        */
        if(i == id[i]){
            return i;
        }
        id[i] = root(id[i]);  
        return id[i];
    }

    public boolean connected(int p, int q) {
        System.out.println(p + " and "+ q+" whether connected: "+(root(p) == root(q)));
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) {
            return;
        }
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
            System.out.println("Attach root("+p+") = "+i+" to root("+q+") = "+j+". Size"
                    + " root("+q+") = "+sz[j]);
        } else {
            id[j] = i;
            sz[i] += sz[j];
            System.out.println("Attach root("+q+") = "+j+" to root("+p+") = "+i+". Size"
                    + " root("+p+") = "+sz[i]);
        }
    }

    public static void main(String[] args) {
        QuickUnionUF qf = new QuickUnionUF(10);
        qf.union(1, 2);
        qf.union(3, 4);
        qf.union(3, 5);
        qf.union(2, 3);
        qf.union(6, 7);
        qf.union(7, 8);
        qf.union(9, 0);
        qf.union(8, 9);
        qf.union(3, 6);
        
        //0 should have root 3 now!
        
        //Notice the change in id[i] after a root() call.
        //The tree is
        System.out.println(qf.id[0]);
        System.out.println(qf.id[9]);
        System.out.println(qf.id[6]);
        System.out.println(qf.id[3]);
        
        System.out.println("Calling root(0)");
        System.out.println(qf.root(0));
        System.out.println("After path compression: ");
        
        System.out.println(qf.id[0]);
        System.out.println(qf.id[9]);
        System.out.println(qf.id[6]);
        System.out.println(qf.id[3]);
        
        //Other elements remain as they were before
        System.out.println("Other elements remain as they were before");
        System.out.println(qf.id[8]);
        
    }
}

Node arrangement for the example used in this program:

Output:

Attach root(2) = 2 to root(1) = 1. Size root(1) = 2

Attach root(4) = 4 to root(3) = 3. Size root(3) = 2

Attach root(5) = 5 to root(3) = 3. Size root(3) = 3

Attach root(2) = 1 to root(3) = 3. Size root(3) = 5

Attach root(7) = 7 to root(6) = 6. Size root(6) = 2

Attach root(8) = 8 to root(7) = 6. Size root(7) = 3

Attach root(0) = 0 to root(9) = 9. Size root(9) = 2

Attach root(9) = 9 to root(8) = 6. Size root(8) = 5

Attach root(6) = 6 to root(3) = 3. Size root(3) = 10

9

6

3

3

Calling root(0)

3

After path compression: 

3

3

3

3

Other elements remain as they were before

6

Quick Sort Implementation [Java]

Quicksort makes O(n log n) comparisions to sort n items. In the worst case, it makes O(n^2) comparisions. Quicksort is often faster in practice than other O(n log n) algorithms. Qucicksort is a comparison sort.

Quicksort is NOT a stable sort.
Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during recursion.

This video has a really nice explanation of the algorithm:

https://www.youtube.com/watch?v=COk73cpQbFQ

Code:

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int array[]) {
        quickSorter(array, 0, array.length - 1);
    }

    public static void quickSorter(int array[], int lo, int hi) {
        if (lo > hi) return;

        int partition = partition(array, lo, hi);
        quickSorter(array, lo, partition - 1);
        quickSorter(array, partition + 1, hi);
    }

    private static int partition(int array[], int lo, int hi) {
        int partitionIndex = lo;

        for (int i = lo; i <= hi; ++i) {
            if (array[i] < array[hi]) {
                int temp = array[partitionIndex];
                array[partitionIndex] = array[i];
                array[i] = temp;
                partitionIndex++;
            }
        }
        int temp = array[partitionIndex];
        array[partitionIndex] = array[hi];
        array[hi] = temp;
        return partitionIndex;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]