Wednesday, December 7, 2011

Algorithms: Bubble Sort in Java



Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
Although the algorithm is simple, it is not efficient for sorting large lists; other algorithms are better.

Worst case performance О(n2)
Best case performance О(n)
Average case performance О(n2)

where n is the number of items being sorted

Formula of Bubble Sort should be n(n-1). For 8 elements there should be 56 possible comparison


public class BubbleSort {

                public static void main(String args[]){
               
                                int[] array={5,3,8,4,6};
                                printArray(array);
                                int comparison=0;
                                for(int j=0;j<array.length;j++){
                                               
                                for(int i=0;i<array.length-1;i++){
                                                int a=array[i];
                                                int b=array[i+1];
                                                comparison++;
                                                if(a>b){
                                                                array[i]=b;
                                                                array[i+1]=a;
                                                }
                                               
                                }
                                }
                                System.out.println();
                                printArray(array);
                                System.out.println();
                                System.out.println(comparison);
                }
               
                public static void printArray(int[] array){
                                for(int i:array){
                                                System.out.print(i+",");
                                }
                }
}


WikiPedia has very good article about Sorting Algorithms


Patterns: Factory Method

Factory Method

Purpose
  1. Define an interface for creating an object, but let subclasses decide which class to instantiate. Factory Method lets a class defer instantiation to subclasses.
  2. Defining a “virtual” constructor.
  3. The new operator considered harmful.

Facotry Method is a Creational Pattern and it deals with Creation of Object without specifying the exact class of object that will be created. Object creation some times requires complex processes not required and it’s not appropriate to write all this code in composing object

Facotry Method design pattern handles this problem by creation of a separate method for creation of object which Subclass can override to provide its own implementation

Essence of Factory Method Pattern is

“Define an interface for creating an object, but let the subclasses decide which class to instantiate. The Factory method lets a class defer instantiation to subclasses”


public class TestFactoryMethod {

      public static void main(String[] args) {
            Skin s=SkinFactory.getSkin("web");
            s.printSkin();
      }          
     
}

class SkinFactory{
      public static Skin getSkin(String type){
            if(type!=null && type.equals("web"))
                  return new WebbasedSkin();
            else
                  return new DesktopbasedSkin();
      }
}

interface Skin{
      public void printSkin();
}

class WebbasedSkin implements Skin{
      public void printSkin(){
            System.out.println("I am Web based Skin");
      }
}

class DesktopbasedSkin implements Skin{
      public void printSkin(){
            System.out.println("I am DesktopbasedSkin Skin");
      }
}



Important Concepts To Remeber during Written Java Test

Point 1)
The code below is executed by "java -Dmyprop=myprop Test". Which two, placed instead of "//some code goes here", will produce the output "myprop"? (Choose two)
public class Test { 
    public static void main(String args[]) {
        String prop = //some code goes here//
        System.out.print(prop);
    }
}
 A) System.getEnv("myprop");
 B) System.load("myprop");
 C) System.property("myprop");
 D) System.getProperty("myprop");
 E) System.get("myprop");
 F) System.getProperties().getProperty("myprop");
Answers: D, F
System.getProperty functions gets the system property indicated by the specified key.


Point 2)
Always Remember
A Static method can call other Static Methods in same class
A Static method can not call other Non Static Methods directly in same class
A Non Static Method can call static method directly

Point 3)
public class Room {
    public int roomNr;
    private Date beginDtm;
    private Date endDttm;
    
    public void book(int roomNr, Date beginDttm, Date endDttm) {
        this.roomNr = roomNr;
        this.beginDtm = beginDttm;
        this.endDttm = endDttm;
    }
}
The variable roomNr breaks encapsulation.

Point 4)
Object myObj = new String[]{"one", "two", "three"}; is valid declaration and initiation

Point 5)
 public void waitForSomething() {
        SomeClass o = new SomeClass();
        synchronized (o) {
            o.wait();
            o.notify();         
        }}
A) This code may throw an InterruptedException
B) This code may throw an IllegalStateException
C) This code may throw a TimeOutException
D) Reversing the ofrer of o.wait() and o.notify() will cause this method to complete normally.
Answer: A.
Object
API:
public final void wait() throws InterruptedException


Point 6)
String s="abcd";
System.out.println(s.charAt(3));

Will print 3 because chatAt starts from 0

Point 7)
Given the code. What is the result?
import java.io.*;
public class Hotel implements Serializable {
    private Room room = new Room();
    
    public static void main(String[] args) {
        Hotel h = new Hotel();
        try {
            FileOutputStream fos = new FileOutputStream("Hotel.dat");
            ObjectOutputStream oos = new ObjectOutputStream(fos);
            oos.writeObject(h);
            oos.close();
        } catch(Exception ex) {
            ex.printStackTrace();
        }
    }
}
class Room {
}
 A) Compilation fails.
 B) An instance of Hotel is serialized.
 C) An instance of Hotel and an instance of Room are both serialized.
 D) An exception is thrown at runtime.
Answer: D.
java.io.NotSerializableException is thrown at runtime. All variables of a class being serialized must be serializable as well.
If Room become transient then its fine private transient Room room = new Room();

Point 8)
      public static void main(String[] args) {

            Integer[] a=new Integer[10];
            printValue(a); // Problem here. Integer can not be passed in Double. Compile time error
      }

      public static void printValue(Double[] d){
            System.out.println(d);}
            public static void main(String[] args) {

            Integer[] a=new Integer[10];
            printValue(a); // Problem here. Integer can not be passed in Long. Compile time error

      }

      public static void printValue(Long[] d){
            System.out.println(d);
      }