Tutorial: Simple Algorithm Analysis

HelloWorld · #1 (**permalink**) 07-17-2007, 12:18 AM

** I just got pissed off because there was Database error for 1s and then got back again (by the time I clicked submit) ** And yeah, didn't save anything that I just wrote... yeah, really long... anyways.. haha... I'm bored anyways!!

Hello all~!
Come back to HelloWorld's Tutorial again!!! It's been a long time that I haven't wrote tutorial, and yeah here it is again, hopefully this tutorial would be helpful for everyone. Please don't hate, blame, or sue me (if you're in the U.S) if you got an F on your homework, test, or whatever you do... (got fired? lol..) Use this at your own risk. However, this tutorial has been tested and works on JVM 1.6 on Eclipse 3.2 Europa

I have had fun for these past days analyzing some algorithm and see the difference at their running time. I choose 3 algorithm that built on each other for this tutorial purpose: Arrays, ArrayList, and Vector

These Data Structures are built on each other:
Array is the foundation
ArrayList is built from Arrays
Vector is built from ArrayList as well as Arrays

However, please note that Vector and ArrayList are just exactly the same thing if you don't use it in the multithreading application. The only difference between Vector and ArrayList is that Vector is SYNCHRONIZED while ArrayList is NOT. So, it is make sense that Vector is running slower on the application that is not multi-threaded. You will see it in this program that you'll be creating as the part of this tutorial. If you're confused on what are all of this means, stop for a while and read the tutorial that I created about multithreading: http://www.programmerstalk.net/thread845.html

Hopefully the code and the comments are self explanatory. There's nothing that's too amazing to explain. However, feel free to throw me any questions regarding this tutorial in this thread

** CODE IS TESTED AND WORK ON JVM 1.6 **

PHP Code:

  [left]import java.util.ArrayList;
import java.util.Random;
import java.util.Vector;

public class AlgorithmTest {

private static int n1 = 10000;
private static int n2 = 100000;
private static int n3 = 1000000;

// Selection Sort Array
public void ArraySelectionSort(int numbers[], int array_size)
{
int i, j;
int min, temp;

for (i = 0; i < array_size-1; i++)
{
min = i;
for (j = i+1; j < array_size; j++)
{
if (numbers[j] < numbers[min])
min = j;
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}

// Selection Sort ArrayList
public void ArrayListSelectionSort(ArrayList<Integer> al)
{
int i, j;
int min, temp;

for (i = 0; i < al.size()-1; i++)
{
min = i;
for (j = i+1; j < al.size(); j++)
{
if (al.get(j) < al.get(min))
min = j;
}
temp = al.get(i);
al.set(i, al.get(min));
al.set(min, temp);
}
}

// Selection Sort Vector
public void VectorSelectionSort(Vector<Integer> v)
{
int i, j;
int min, temp;

for (i = 0; i < v.size()-1; i++)
{
min = i;
for (j = i+1; j < v.size(); j++)
{
if (v.get(j) < v.get(min))
min = j;
}
temp = v.get(i);
v.set(i, v.get(min));
v.set(min, temp);
}
}

public static void main(String[] args) {
Random r = new Random();

double t1, t2;
double res;

int arr[] = new int[n1];
ArrayList<Integer> al = new ArrayList<Integer>();
Vector<Integer> v = new Vector<Integer>();

// populate
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt(1000000);
al.add(r.nextInt(1000000));
v.add(r.nextInt(1000000));
}// end populate

// Arrays
// instantiate this class
AlgorithmTest at = new AlgorithmTest();
t1 = System.nanoTime();
at.ArraySelectionSort(arr, n1); // add populated Arrays
t2 = System.nanoTime();
res = t2 - t1;
System.out.println("Array: " + res);

// ArrayList
t1 = System.nanoTime();
at.ArrayListSelectionSort(al); // add populated ArrayList
t2 = System.nanoTime();
res = t2 - t1;
System.out.println("ArrayList: " + res);

// Vector
t1 = System.nanoTime();
at.VectorSelectionSort(v); // add populated vector
t2 = System.nanoTime();
res = t2 - t1;
System.out.println("Vector: " + res);
}
}
[/left]

The result that I get: (may vary)

Code:

Array: 1.6671426E8 ArrayList: 1.40868954E9 Vector: 8.764331389E9

Pay attention that it's E8, E9, and E9.. I assume that you know what are those means

Note that Vector must be the slowest from all 3 because of the explanation that I made earlier.

Thanx to whoever that helped me: Java API and my brain..

FOR ALL OF MY CLASSMATES: Better not just copy and paste! but well, you're lucky for coming to this site

#2 (**permalink**) 07-17-2007, 11:21 PM

Very nice, however, your code seems to work only with n1. When I replace n1 with either n2 or n3, it throws an ArrayIndexOutOfBoundsException.

The error points to the line if (numbers[j] < numbers[min]) in the ArraySelectionSort
and the line where we take in n1, n2 or n3.

HelloWorld · #3 (**permalink**) 07-17-2007, 11:25 PM

Hehe, thanx for reminding me to test them over again at least

But when I tested it, it works perfectly fine. That's probably you have not changed both n2 on:

Code:

int arr[] = new int[n2];

Code:

        at.ArraySelectionSort(arr, n2); // add populated Arrays

It takes a while for me to complete the task though

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

The Following User Says Thank You to HelloWorld For This Useful Post:
Leech (07-17-2007)

The Following User Says Thank You to For This Useful Post:
HelloWorld (07-17-2007)