No Compelling Content

I’ve been working on implementations of various Java programs and the like in my Data Structures and Algorithms class, and since I really like how this turned out, I figured it’d be worth sharing.

This is the first time I’ve used multiple buttons and the default UI layout – I think it’d be nice to share an implementation of it. This program also has a delightful side effect of showing how close heap sort works to O(n log(n)). Code follows:

main.class

// thanks to ping for heapsorter as well as rolf's colorbox
// Heapsort was originally published by J.W.J. Williams as
// Algorithm 232 in the journal Communications of the ACM [Wil 64].

package lab10;

public class Main{

    private static int[] a;
    private static int n;
    static int[] w1;

    static int w = 2000;
    static ColorBox b1 = new ColorBox(w);

    public static void main(String[] args) {
     //   int w = 600;
     //   ColorBox b1 = new ColorBox(w);
    }

    static int dh = 0;
    static int sc = 0;

    public static void sort(int[] a0)
    {
        a=a0;
        n=a.length;
        heapsort();
    }

    private static void heapsort()
    {
        buildheap();
        while (n>1)
        {
            n--;
            swap (0, n);
            downheap (0);
        }
    }

    private static void buildheap()
    {
        for (int v=n/2-1; v>=0; v--)
            downheap (v);
    }

    private static void downheap(int v)
    {
        int k =  2*v+1; //k = root's children
        while (k<n)
        {
            if (k+1<n)
                if (a[k+1]>a[k]) k++;
            if (a[v]>=a[k]){
                return;
            }
            swap(v, k);
            v=k;
            k=2*v+1;
            dh++;
        }
    }

    private static void swap(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
        sc++;
    }
}

/*
 * Okay, these are the numbers I'm getting for the swaps needed for each job
 * When I say "should be" number x, I'm speaking of the following formula for
 * the O(n logn) amount of swaps required...
 * 
 * x | x is a side of the array
 * swaps = x^2 * lb(x^2)  
 * where lb is binary log.
 *
 * Since big O notation reperesents an >upper< bound after a certain nominal value
 * none of the trials should be larger than O(n log n).
 *
 *
 * size: 100
 * swaps: 123891
 * Should be ~130k
 * http://www.wolframalpha.com/input/?i=100%5E2+%2A+lb%28100%5E2%29
 *
 * size: 200
 * swaps: 575216
 * Should be about ~611k swaps
 * http://www.wolframalpha.com/input/?i=200%5E2+%2A+lb%28200%5E2%29
 *
 * size: 300
 * swaps: 1399854
 * Should be about ~ 1.4 million swaps
 * http://www.wolframalpha.com/input/?i=300%5E2+%2A+lb%28300%5E2%29
 *
 * size: 400
 * swaps: 2,619,194
 * Should be about 2.7 million swaps
 * http://www.wolframalpha.com/input/?i=400%5E2+%2A+lb%28400%5E2%29
 *
 * size: 500
 * swaps: 4,248,474
 * Should be ~ 4.4 million swaps
 * http://www.wolframalpha.com/input/?i=500%5E2+%2A+lb%28500%5E2%29
 *
 * size: 1000
 * swaps: 18,986,697
 * Should be 19 million swaps
 * http://www.wolframalpha.com/input/?i=1000%5E2+%2A+lb%281000%5E2%29
 *
 * size: 1500
 * swaps: 45,343,618
 * should be about ~ 47 million swaps
 * http://www.wolframalpha.com/input/?i=1500%5E2+%2A+lb%281500%5E2%29
 *
 * size: 2000
 * swaps: 83914749
 * should be about ~ 87 million
 * http://www.wolframalpha.com/input/?i=2000%5E2+%2A+lb%282000%5E2%29
 *
 */

next, we have the ColorBox method provided by the Professor and it includes my added buttons. This is the first time I’ve ever implemented multiple buttons on the UI. I know, minor victory. But that, to me, is really what programming is all about – little victories until one day, bam, you are half competent.

ColorBox.class

/*
 * ColorBox.java
 * Created on November 1, 2007, 11:08 AM
 * by Rolf Lakaemper
 * Zach added the buttons and actions
 */

package lab10;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;

public class ColorBox extends JPanel implements ActionListener{

    private static final int DEFAULTSIZE = 400;
    private int []colors;
    private int size;

    //zach's buttons
    public JButton j1;
    public JButton j2;
    public JButton j3;

    /* Creates a new instance of ColorBox */
    public ColorBox(int inSize) {

        size = inSize;
        colors = new int[size*size];
        initRandom();

        // Visuals
        setPreferredSize(new Dimension(size,size));
        JFrame frame = new JFrame("ColorBox");
        add(j1 = new JButton("sort"));
        add(j2 = new JButton("randomize"));
        add(j3 = new JButton("downheaps and swaps"));

        j1.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent ae) {
                Main.w1 = Main.b1.getColorValues();
                Main.sort(Main.w1);
                Main.b1.setColorValues(Main.w1);}
        });

        j2.addActionListener(this);

        j3.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent aw) {
                System.out.println("size: " + size);
                System.out.println("downheaps: " + Main.dh);
                System.out.println("swaps: " + Main.sc);}
        });
        
        
        frame.setDefaultCloseOperation(frame.EXIT_ON_CLOSE);
        frame.getContentPane().add(this);
        frame.pack();
        frame.setVisible(true);

    }

    /* Creates a new instance of ColorBox */
    public ColorBox() {
        this(DEFAULTSIZE);
    }

    public void initRandom(){
        for (int i=0;i<colors.length;i++){
            colors[i]=(int)(Math.floor(Math.random()*256));
        }

    }

    public int[] getColorValues(){
        // return a COPY of colors, keeps colors private
        int []c=new int[colors.length];
        System.arraycopy(colors,0,c,0,colors.length);
        return(c);
    }

    public void setColorValues(int []c){
        if (c.length!=colors.length){
            System.out.println("Error, arrays of different size.");
        }
        else{
            System.arraycopy(c,0,colors,0,colors.length);
        }
        repaint();
        return;
    }

    public void paintComponent(Graphics g){
        int count = 0;
        for (int row=0;row<size;row++){
            for (int r=row;r>=0;r--){
                g.setColor(new Color(colors[count],0,0));
                count++;
                g.drawLine(row-r,r,row-r,r);
            }
        }
        for (int col=1;col<size;col++){
            for (int c=col;c<size;c++){
                g.setColor(new Color(colors[count],0,0));
                count++;
                g.drawLine(c,size-c+col-1,c,size-c+col-1);
            }
        }
    }

    public static void main(String []args){
        ColorBox cb = new ColorBox(500);
        int []c=cb.getColorValues();
        java.util.Arrays.sort(c);
        cb.setColorValues(c);
    }

    public void actionPerformed(ActionEvent e) {
    // randomize button
       initRandom();
       repaint();

    // get ready for another run by setting counters to zero
    // downheap set back to zero
       Main.dh = 0;
    // swap count set back to zero
       Main.sc = 0;


    //  Junk drawer from other implementations/versions...

    //  long time1 = System.currentTimeMillis();
    //  Main.w1 = Main.b1.getColorValues();
    //  Main.sort(Main.w1);
    //  Main.b1.setColorValues(Main.w1);
    //  long time2 = System.currentTimeMillis();
    //  System.out.println(time2-time1);
    }
}