by zach @ . November 26, 2010 . 3:59AM
by Zacharias @ http://inexactitu.de . November 22, 2010 . 5:45PM
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);
}
}
by zach @ . November 19, 2010 . 3:59AM
by zach @ . November 12, 2010 . 3:59AM
by Zacharias @ http://inexactitu.de . November 11, 2010 . 11:21AM
remember that depending on your particular architecture, you can get some really strange results. As an example, on my macbook pro, I ran an application that polls the counter and asks it how many cycles it’s had since it was powered on. Thats how the spec works, anyways. I was getting some strange results I couldn’t explain, and it turns out every time rtdsc() was called, it was asking the other processor core.
Which wasn’t on when polled.
This meant that every other time it was asked, it was waking up a processor to say, eh, I’ve been awake for 287/24000000000 of a second.
I re-ran the results connected to a Unix server and got the right results.
So it goes. Click on the image below and experience the magic for yourself.
by Zacharias @ http://inexactitu.de . November 9, 2010 . 1:51PM
In hopes of recalling elementary string functions in C, I’m jotting this down with comments.
It makes a lot of sense to really understand library functions before you go and try to re-make Doom.
int strcmp (char *s, char *t)
{
for ( ; *s == *t; s++, t++)
if (*s == '\0')
return 0;
return *s - *t;
}
So first we look at the input: we have two char pointers. Since we don’t have to change either s or t in order to compare them, pointers are the most efficient way to refer to them.
There is three possible input situations, first s could be greater than t, t could be larger, or they could be the same. Implicitly, we are comparing s to t. The for loop at the first line is made to go until s and t become not equal or to report they’re equal if the end of line \0 enters.
Otherwise, the difference between the two strings are reported as the result. This will be positive if s is longer than t, or negative if t us larger.
Therefore we have a discrete output for each of the three conditions. Note that since this comparison (in the for loop) is done until the end of similarity, the worst-case order of magnitude for this function is O(n). All other cases are O(1).
by zach @ . November 5, 2010 . 3:59AM
by Zacharias @ http://inexactitu.de . November 4, 2010 . 8:59PM
Anyways, here’s a picture I took outside my office on a (not very) rare goofing off break.
