Wednesday, April 17, 2013

Bubble Sort algorithm

The Bubble Sort algorithm is named as such after the way in which values bubble to the top.

It is a suitable sorting algorithm for small unsorted lists and arrays.

You may like to watch the video at the end of this post before reading on (skip to about 50 seconds in).

Let's take the example of a small array of 5 elements:

int numList[] = {100,40,2,1,89};

In it's sorted form, the list of numbers would look like this:

1,2,40,89,100

So how do we get there?

Using a for-loop, we will bubble sort the values by checking if the current value is greater than the next value in the array:

for (int x = 0; x < numList.length - 1; x++) {

if (numList[x] > numList[x+1] )

If true, we need to swap the numbers in the array, but to do so, we will need to store the current value in a temporary variable, so that the next value can be placed into the current value's place in the array - like so:

int temp = numList[x];
numList[x] = numList[x+1];
numList[x+1] = temp;




If false, we do nothing and allow the loop to continue.

Note that the loop is primed so that the loop counter (x) is never greater than the array's length minus one - which in this example would mean that x is never greater than 3. This is because the final swap possible is between indexes 3 & 4 and we don't want to generate an ArrayIndexOutOfBoundsException when we execute the expression numList[x+1].

If the length of the list we need to sort is 5, it will take 4 loops to sort the list, once.

First pass:
100,40,2,1,89 becomes 40,2,1,89,100

We can see that 100 has bubbled to the end of the list, however, the list is still not sorted. If the length of the list is 5, it will take 16 loops (maximum) to ensure that each position is sorted.

We will need to use an outer loop and and inner loop (nested loops) to ensure that all elements are sorted.


And here is the output of each outer loop:


Note that in this example, it actually only took 3 outer loops (12 loops total) to sort the array. If we used the following array:

5,4,3,2,1

... it would take 16 repetitions to sort the array completely - this is because the largest number in the array (5) is in the first position and therefore has the entire length of the array to be sorted through.

Here's the output of bubble sorting that list:



The video is quite cool :)




Tuesday, April 16, 2013

The For loop


Loops allow us to perform a set of instructions repeatedly until a certain condition is reached.

A video game is basically a continuous loop that handles input, handles updates and draws - maybe 60 times per second!

There are a few different kinds of loops. This post is about the For-Loop, however all loops have some things in common:

  • A loop needs a start condition - where to start
  • A loop needs an end condition - where to end
  • A loop contains a body - the statements to execute repeatedly.

If a loop does not know where to end, we get an INFINITE LOOP and that's really no good.

The For-Loop
The for-loop is primed with the following information about the loop:

  • The value of the loop counter when the loop starts - initialization
  • The value that flags the end of the loop - termination
  • How the loop counter should be incremented on each pass of the loop - increment

Format of the syntax:

for (initialization; termination; increment) {
    statement(s)
}


Note:

  • The increment condition may also be a decrement condition.
  • The loop counter can begin at any value - for instance 0 or 1000 (it depends on the task).


The body of the loop is where we place the instructions which need to be repeated.

In the following example, the numbers 0 to 9 are printed to screen. The loop has been primed to start the counter variable at 0. The loop will continue while the counter variable is less than 10. The counter variable will be incremented on each pass of the loop.



In the following example, the numbers 10 to 0 are printed to screen. The loop has been primed to start the counter variable at 10. The loop will continue while the counter variable is greater than 0. The counter variable will be decremented on each pass of the loop.



"The for Statement (The Java™ Tutorials > Learning the Java Language > Language Basics)" ( http://bit.ly/ZtqqHM )

Wednesday, April 10, 2013

TreeMap


  • The TreeMap is part of the Java Collections Framework.
  • TreeMap is a concrete class which implements the Map interface, which maps keys to values. 
  • Keys are like the index of an ArrayList except that the index of an ArrayList is an int. A map key can be any object.
  • A map cannot contain duplicate keys - each key maps to one value.
  • A key and it's corresponding value form an entry or entry-set. Let's call them key/value pairs.
  • A TreeMap is sorted by the natural ordering of it's keys.


Instantiation
Map<key,Value> = new TreeMap<Key,Value>();

(As map is an Interface, it cannot be instantiated.)

get(Object key)
Returns the value for the specified key. If a value at that key does not exist, null is returned. While this is most forgiving, always check the return value for null before attempting to use it.

Object o = myMap.get(x);
if (o != null) {...};


containsKey(int key)
Returns True if the specified key is found in the map. (False is not!).

if (myMap.containsKey(x)) {...};


put(Object key, Object value)
Puts the new value at the specified key. If the key already exists, the old value is replaced. So be careful!

myMap.put(x,o);

size()
Returns the number of key/value pairs.

myMap.size();

remove(int key)
Removes the value at the specified key. If no value as associated with the key, the method simply exits.

myMap.remove(x);

putAll(Map)
Copies all of the mappings from the specified map, to this map. Both maps must have the same key and value type. Beware though, if there are values for identical keys, the old value will be replaced with the new value - as per the *no duplicates* rule.
For instance:

Map<Integer, String> mapOne = new TreeMap<Integer,String>();
mapOne.put(10, "ten");
mapOne.put(3, "three");

Map<Integer,String> mapTwo = new TreeMap<Integer,String>();
mapTwo.put(50, "fifty");
mapTwo.put(10, "ten");

mapOne.putAll(mapTwo);

mapOne now contains the following key/value pairs (sorted):

  • 3, "three"
  • 10, "ten"
  • 50, "fifty"


Iterating (looping) using Enhanced For Loop

The following methods are utilised in the enhanced for loop example below:

  • entrySet() returns a view of the key/value pairs in the map.
  • getKey() returns the key in the current iteration.
  • getValue() returns the value of the key in the current iteration

In plain English, we are saying that for each Integer and String, key/value pair in the map.


for (Map.Entry<Integer, String> mapEntries : mapOne.entrySet()) {
      int key = mapEntries.getKey();
      String value = mapEntries.getValue();
      System.out.println("Key is: " + key);
      System.out.println("Value is: " + value);
}

We would expect the output to look like:

3
three
10
ten
50
fifty

Pulling keys or values out of Map and into ArrayList

In this example, a map of Integer,Integer is split into two lists - one for keys and one for values.

List<Integer> listOfMapKeys = new ArrayList<Integer>(mapname.keySet());
List<Integer> listOfMapValues = new ArrayList<Integer>(mapname.values());


But the coolest stuff is yet to come!!! Read on in NavigableMap Interface >>>

(also, will post code download soon too!)

(also, IS ANYONE READING THIS?) :p








NavigableMap Interface

......

Enhanced For Loop

Also called the For-each loop.



For each Line in the array called myLine.

Also see:

"Using Enhanced For-Loops with Your Classes" ( http://bit.ly/15bt7V5 )
"Java: For-each Loop" ( http://bit.ly/HThpAk )


Tuesday, March 12, 2013

Java Math basics

Maths Operators

The maths operators in the figure below, probably look familiar.

The basic set of Java arithmetic operators is presented in the figure.

  • Multiplication

  • Division

  • Modulo

  • Addition

  • Subtraction

The operators have been split into two groups to indicate their ‘precedence’ - the order in which they are obeyed.

 

Order of precedence

Multiplication, division and modulo operations are carried out before addition and subtraction.

If a calculation contains operators of the same precedence, the calculation is performed from left to right.

int j;
    int n = 2;
    j = n + 5; // Set to to 7
    j = n * 2; // Set to 4
    j = 3 + 3 * 2; // Set to 9
    j = n * ( 5 + 2 ) * 2 // Set to 28
    j = 25 - 3 // Set to 22

We can use parenthesis (brackets) to group calculations and force them to be carried out in a particular order.

Wherever brackets are used, the items within them are calculated first.

For instance, the sum 10 + 20 multiplied by 100 produces the result 3000. It could be tempting to write that equation as follows:

     10 + 20 * 100

However, due to the order of precedence in which arithmetic operations are performed, the sum is performed as if it had been written 10 + ( 20 * 100 ) producing the result 2010.

Note: Spaces are only required on either side of an operator for easy readability.

Integer Division

The Integer data type is a whole-number numeric data type. Where integer division is being performed, only the integer part of the result is returned.

For instance, if you type 13 / 5 into a calculator, you will see the result is 2.6.
However, when you perform integer division in a programming language, such as Java, the result of the same calculation is 2 - only the integer (whole number) part is returned as the result.

Double Division

The double data type is a floating point numeric data type..

Where double division is performed, the result is returned as a floating point number. Once again, using the example of 15 / 5, the result returned from double division is 2.6.

The % operator (modulo)

This operator returns the remainder of division of one number by another number.

int examples

For instance, 10 / 2 has a remainder of 0. This is because 10 is divided by 2 exactly.

Another example, 15 / 2 has a remainder of 1. This is because, after division has taken place (15 can be divided 7 times), 1 is left over.

More examples:

    int x;
    x = 12 % 4; // Set to 0
    x = 12 % 3; // Set to 0
    x = 12 % 5; // Set to 2
    x = 50 % 7; // Set to 1
    x = 100 % 33; // Set to 1
    x = 100 % 5; // Set to 0
    x = 30 % 9; // Set to 3

Remember, the remainder of an integer division only returns the integer part of the result.
 
For instance, if you were to type 4 / 3 into a calculator, you would see the result is 1.3333333 etc. However, where this calculation is being performed as integer division in a programming language, such as java, only the integer part is returned - producing the result 1.

Using % to convert cents into dollars

Let’s say we want to convert an int amount of cents (577) into dollars and cents.
The algorithm is as follows:

inputs - numOfCents
outputs - numOfDollars, centsRemaining
processing tasks -
    • get numOfCents
    • numOfDollars = numOfCents / 100
    • centsRemaining = numOfCents % 100


Remember, integer division returns the integer part of the result, so the statement

    dollars = numOfCents / 100

will return 5, in this example.

Monday, March 4, 2013

Overriding Methods

Method overriding allows us to provide our own implementation of a method in a child class.

"Overriding and Hiding Methods (The Java™ Tutorials > Interfaces and Inheritance)" ( http://bit.ly/Zn8eop )

"Polymorphism (The Java™ Tutorials > Learning the Java Language > Interfaces and Inheritance)" ( http://bit.ly/PYQDIV )