Wednesday, January 28, 2009

Selection Sort in Python

Selection sort is a very simple sorting mechanism. It looks through the remaining items in the input to find the least one and moves it to its final position. It is an in-place sort and has a complexity of O(n²) . Here is an implementation of it in Python.

import types

def doSelectionSort(input):
"Check for a few simple error conditions"
if input == None:
raise Exception("Input cannot be null")
if not type(input) is types.ListType:
raise Exception("Input can only be a List")

"Do the sort"
length = len(input)
if length <= 1: "Input is already sorted" return i = 0 while i < smallest =" i" j =" i" smallest =" j" temp =" input[i]" a =" [3,6,8,2,0,9,5,89,9]" b =" []" c =" (3,4)">

Here is the ouput:
[0, 2, 3, 5, 6, 8, 9, 9, 89]
[]
Input can only be a List

Thursday, January 22, 2009

Quicksort implementation in Java

Quicksort is a well known sorting algorithm. You can find more information about it here. Following is an implementation of Quicksort in Java with generics.

public class QuickSort {

/**
* Quicksort using Java generics
* @param a an array of Comparable items.
*/
public static <T extends Comparable<T>>
void doQuickSort(T[] a) {
if (a == null) {
throw new
IllegalArgumentException("Input Array cannot be null");
}
int length = a.length;
if (length == 1) return;
doQuickSort(a, 0, length-1);
}

/**
* Actual quicksort implementation using
* median of 3 partitioning.
* @param a an array of Comparable items.
* @param left the left index of the subarray.
* @param right the right index of the subarray.
*/
private static <T extends Comparable<T>> void
doQuickSort(T[] a, int left, int right) {

//Base case
if (left >= right) return;

//Choose the pivot using median of 3 partitioning
//using the following 2 steps
//First step: find the center
int center = (left+right)/2;
//Second step: sort left, center and right
if (a[left].compareTo(a[center]) > 0) {
swap(a, left, center);
}
if (a[left].compareTo(a[right]) > 0) {
swap(a, left, right);
}
if (a[center].compareTo(a[right]) > 0) {
swap(a, center, right);
}
//Third Step:
//Got the pivot and it is at the center.
//Move it to the end of the array.
swap(a,center,right-1);
int pivot = right-1;

//Partition the array
int i = left,j = right - 2;
if (j >= 0) {
for(;;) {
while (a[i].compareTo(a[pivot])< 0) {
i++;
}
while(a[j].compareTo(a[pivot]) > 0) {
j--;
}
if (i >= j) break;
swap(a,i,j);
}
}
//Put the pivot at ith position of the array
swap(a,i,right-1);
//Now all the elements to the right of i are less than
//it and all the elements to the left of i are greater
//than it. So partition the array and
//recursively call quicksort on the left and right partition
doQuickSort(a, left, i-1);
doQuickSort(a, i+1, right);

}

/**
* Internal method to swap to elements in an array.
* @param a an array of objects.
* @param left the index of the first object.
* @param right the index of the second object.
*/
private static <T extends Comparable<T>>
void swap(T[] a, int left, int right) {
T temp = a[left];
a[left] = a[right];
a[right] = temp;
}

//Test it
public static void main(String[] args) {
Integer[] input = {5,14,16,2,17,1,8,6,0,9};
doQuickSort(input);
printArray(input);
String[] str = new String[]{"adc","abc", "acd", "aaa"};
doQuickSort(str);
printArray(str);
}

/**
* Internal method to print the elements in an array.
* @param a an array of objects.
*/
private static <T extends Comparable<T>>
void printArray(T[] a) {
for (T elem: a) {
System.out.println(elem);
}
}

}



Output on running the above program:
0
1
2
5
6
8
9
14
16
17
aaa
abc
acd
adc

Sunday, January 18, 2009

Using google-code-prettify to highlight code in web page

I wanted to highlight my code in blogger and stumbled upon this from google. It also nicely formats the code. Henceforth, I am going to use prettify and not this. Here are the steps to do it.

- Edit your template in the dashboard (Layout->Edit HTML, see pic below)



- Include these two lines in the head tag.

< link href="http://google-code-prettify.googlecode.com/svn/trunk/src/prettify.css" type="text/css" rel="stylesheet">
< script type="text/javascript" src="http://google-code-prettify.googlecode.com/svn/trunk/src/prettify.js" > </script>


- Change the body tag to include onload='prettyPrint()'

< body onload='prettyPrint()'>

- Save the template.

- Now to highlight your code do this

< pre class="prettyprint">
... # Code goes here
</pre>


Thats it. Here is an example:

public class Factorial {

public static int getFactorial(int input) {
int fact = 1;
if (input==0 || input==1) return fact;
if (input < 0) fail("Provide argument >= 0");
for (int i = 2; i <= input; i++) {
fact = fact*i;
}
return fact;
}

public static void fail(String exception) throws
IllegalArgumentException{
throw new IllegalArgumentException(exception);
}

}

Friday, January 9, 2009

Using java properties

Properties

Using the java.util.Properties API, properties(key=value pairs) can be read from files. The properties can be listed, modified and can be saved to files. An example is shown below.

public class MyFileProperties {
public static final String appPropFile = "Props";
public static void main(String[] args) throws IOException{
FileInputStream fs = null;
FileOutputStream fos= null;

try {

//Load application's properties from a file
fs = new FileInputStream(appPropFile);
Properties myProps = new Properties();
myProps.load(fs);

//Check if the application has any properties
System.out.println(myProps.isEmpty());

//Add new properties to the application
myProps.setProperty("application.name","My Properties");
myProps.setProperty("application.version","1.0");

//List the properties as key=value pairs
myProps.list(System.out);

//Print only keys of properties
Set<String> s = myProps.stringPropertyNames();
String[] properties = s.toArray(new String[0]);
for (String prop: properties){
System.out.println("Property Name: " + prop);
}

//Save the application properties back to the file
fos = new FileOutputStream(appPropFile);
myProps.store(fos, "last updated " + new java.util.Date());

} catch (FileNotFoundException fe) {
fe.printStackTrace();
} catch (IOException ie) {
ie.printStackTrace();
} finally{
if (fos != null) fos.close();
if (fs != null) fs.close();
}

}

}


The output is shown below:
false
-- listing properties --
nikki=akku
application.name=My Properties
application.version=1.0
hello=world
application.release=7
ann=kutty
Property Name: nikki
Property Name: application.name
Property Name: application.version
Property Name: hello
Property Name: application.release
Property Name: ann

The properties file is shown below:
#last updated Tue Mar 17 00:56:04 PDT 2009
#Tue Mar 17 00:56:05 PDT 2009
nikki=akku
application.name=My Properties
application.version=1.0
hello=world
application.release=7
ann=kutty

Properties and XML files

JDK 1.5 introduced APIs to load and store properties from/to XML files. The document must satisfy the DTD described here. An example is shown below.



public class MyXMLProperties {
public static void main(String[] args) throws IOException{
FileInputStream fx = null;
FileOutputStream fox = null;

try {
Properties myProps = new Properties();

//Load properties from an XML file
fx = new FileInputStream("releasexml.xml");
myProps.loadFromXML(fx);

//Add new properties to the application
myProps.setProperty("application.name","My Properties");

//List the properties as key=value pairs
myProps.list(System.out);

//Save the properties to a XML file
fox = new FileOutputStream("XMLProps.xml");
myProps.storeToXML(fox, null);

} catch (FileNotFoundException fe) {
fe.printStackTrace();
} catch (IOException ie) {
ie.printStackTrace();
} finally{
if (fox != null) fox.close();
if (fx != null) fx.close();
}
}
}

The output is shown below:

-- listing properties

application.name=My Properties

application.release=7


The XML file is shown below:
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE properties SYSTEM "http://java.sun.com/dtd/properties.dtd">
< properties>
< entry key="application.name"> My Properties</entry>
< entry key="application.release"> 7</entry>
</properties>

System Properties

Using the getProperty() or the getProperties() method of java.lang.System one can get the properties of the OS and Java. Also new system properties can be added or existing ones can be deleted. If one does not have the permissions, a security exception could be thrown at runtime. An example is shown below.


public class MySystemProperties {

public static void main(String[] args) {

//Get the system properties
Properties sysProp = System.getProperties();

//Print all the system properties
sysProp.list(System.out);

//Get a system property.
String javaVersion = System.getProperty("java.version");
System.out.println("Java Version is " + javaVersion);

//Add a system property
System.setProperty("admin.name", "foobar");
System.out.println("Admin name is " + System.getProperty("admin.name"));

//Delete a system property, need to have privileges to do this
System.clearProperty("admin.name");
System.out.println("Admin name is " + System.getProperty("admin.name"));

}

}


The output is shown below:

-- listing properties --
java.runtime.name=Java(TM) SE Runtime Environment
sun.boot.library.path=C:\Program Files\Java\jre1.6.0_04\bin
.........

sun.desktop=windows
sun.cpu.isalist=pentium_pro+mmx pentium_pro pentium+m...
Java Version is 1.6.0_04
Admin name is foobar
Admin name is null