Bubble Sort Algorithm in Java

Bubble Sort is the simplest sorting algorithm. It works by iterating the input array from the first element to last, comparing each pair of elements and swapping them if needed.
It continues its sort until no swaps are needed. The algorithm got its name the way smaller elements “bubble” to the top of the list.

Generally, insertion sort has better performance than bubble sort.

The only advantage of bubble sort over other implementation is that it can detect whether the input is already sorted or not. Also known as comparison sort.

Let take an array of input:

1 5 4 2 8

In first loop, it will iterate the entire element from 0^th index to 4^th index

Pass 1:

1 5 4 2 8 -> 1 5 4 2 8  no swap because 1>5 fails
1 5 4 2 8 -> 1 4 5 2 8 no swap because 5>4 fails
1 4 5 2 8 -> 1 4 2 5 8 no swap because 5>2 fails

1 4 2 5 8 -> 1 4 2 5 8 no swap

Pass 2

1 4 2 5 8 -> 1 4 2 5 8 no swap

1 4 2 5 8 -> 1 2 4 5 8 swap occur because 4>2

1 2 4 5 8 -> 1 2 4 5 8 no swap

Pass 3:

1 2 4 5 8 -> 1 2 4 5 8 no swap

1 2 4 5 8 -> 1 2 4 5 8 no swap

Pass 4:

1 2 4 5 8 -> 1 2 4 5 8 no swap

Output:

1 2 4 5 8

If you see above, when the array is already sorted it will iterate over the array that why this algorithm complexity is O(n^2) even in best case.

We can improve it by using one Boolean flag. When there is no swap means array is  already sorted, then we can skip the remaining process.

This modified version improved the best cast of bubble sort to O(n).

Performance :

• Worst Case Complexity : O(n^2)
• Best Case Complexity (improved) : O(n) 
• Average Case Complexity : O(n)

If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...

Insertion Sort Algorithm in Java

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It’s much less efficient on large list.

1. Get a hand of unsorted card.
2. We divide the card as sorted and unsorted by placing a marker after the first card.
3. Repeat steps 4 to 6 until unsorted section is empty
4. Select the first unsorted card.
5. Swap this card to left until it arrives at the correct sorted position.
6. Advance the marker to the right one 

Let take a deck of unsorted card (step 1).

7 8 5 2 4 6 3
Now we divide this into two portion one is sorted and another is unsorted (step 2).

7|8 5 2 4 6 3

Here we select the first unsorted card i.e., 8 (step 4). Since 8 is greater than 7 so we do not need to swap the card (step 5).

Advance the marker to the right (step 6)

7 8|5 2 4 6 3

Now we select the next unsorted card i.e. 5. Since 5 is less than 8, so we swap the card

7 5|8 2 4 6 3

Since 5 is still less than 7 we swap again until it is corrected sorted position.

5 7|8 2 4 6 3

Advance the marker.

5 7 8|2 4 6 3

Now we put 2 in the right position.

5 7 2|8 4 6 3

5 2 7|8 4 6 3

2 5 7|8 4 6 3

Advance the marker

2 5 7 8 |4 6 3

Now we put 4 in the right position.

2 5 7 4 |8 6 3

2 5 4 7 |8 6 3

2 4 5 7 |8 6 3

Advance the marker

2 4 5 7 8|6 3

Now we put 6 in the right position.

2 4 5 7 6|8 3

2 4 5 6 7|8 3

Advance the marker

2 4 5 6 7 8|3

Now we put 3 in the right position.

2 4 5 6 7 3|8

2 4 5 6 3 7|8

2 4 5 3 6 7|8

2 4 3 5 6 7|8

2 3 4 5 6 7|8

Advance the marker

2 3 4 5 6 7 8|Here is out sorted output.

Demo : 6 5 3 1 8 7 2 4 

Improved Version : If element are already sorted to its left means no swap is required then we can simply comes out of the loop.

Performance :

• Worst Case Complexity : O(n^2) The simplest worst case input is an array sorted in reverse order. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element
• Average Case Complexity : O(n^2) that why which makes insertion sort impractical for sorting large arrays.
• Best Case Complexity : O(n) When is array is already sorted. During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

Q. For insertion sort, the number of entries we must index through when there are n elements in the array is
Ans : n-1


If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...

Upcasting and Downcasting in java

You can cast an object to another class type, but only if the current object type and the new class type are in the same hierarchy of derived classes, and one is a super-class of the other. Upcasting and downcasting are important part of java. The concept of Polymorphism can help you to better understand the meaning of upcasting and downcasting.

You can cast a reference to an object of a given class type upwards through its direct and indirect superclasses. For example, you could cast a reference to an object of type Spaniel directly to type Dog, type Animal, or type Object. You could write:

Spaniel aPet = new Spaniel(“Fang”);
Animal theAnimal = (Animal)aPet;
Dog theDog = (Dog)aPet;
Object theObject = (Object)aPet;

When you are assigning an object reference to a variable of a superclass type, you do not have to include the cast. You could write the assignment as:
Animal theAnimal = aPet;  // Cast the Spaniel to Animal
This would work just as well. The compiler is always prepared to insert a cast to a superclass type when necessary.

In simple term, we define polymorphism as " Having multiple forms" or " Having many forms". Consider the following. Ask yourself what is rectangle? Most would say its shape. A square,  circle and a triangle are also shapes. What I'm saying is that shape can take many forms or has multiple forms.

Polymorphism in Java
Class inheritance is not just about reusing classes that you have already defined as a basis for defining a new class. It also adds enormous flexibility to the way in which you can program your applications, with a mechanism called polymorphism. So what is polymorphism?

The word polymorphism generally means the ability to assume several different forms or shapes. In programming terms it means the ability of a single variable of a given type to be used to reference objects of different types and to automatically call the method that is specific to the type of object the variable references. This enables a single method call to behave differently, depending on the type of the object to which the call applies

First we create a base class shape. This base class implement a constructor that will accept 2 arguments and a method that will draw out shape.

We need to make out method draw() to behave polymorphically.

What we have done is created an array of the type Shape. Because Square and Circle are derived from Shape, we are able to put them in our array. What we are then doing is looping through all the elements of our array and calling draw for each of our types. Because we have overridden the draw method in each of our derived classes the output of our code is:
Draw a shape at 100,100
Draw a square at 200,200
Draw a circle at 300,300
If we did not override Draw in one of our derived classes, the base class implementation of Draw would be called

Upcasting and Downcasting
First, you must understand, that by casting you are not actually changing the object itself, you are just labeling it differently. For example, if you create a circle and upcast it to shape, then the object doesn't stop from being a circle. It's still a circle, but it's just treated as any other shape and it's circle properties are hidden until it's downcasted to a circle again.

Circle c=new Circle();

System.out.println(c);

Shape s=c;

System.out.println(s);

Output will be look like this :
Circle@12b6651
Circle@12b6651

As you see circle is still exactly the same after upcasting, it didn't change to shape, its just being labeled as shape. This is allowed because circle is a shape.
There is no need to do upcasting manually, its allowed to do.
Shape s = (Shape)new Circle();
same as
Shape s = new Circle();

But downcasting must always be done manually:
Circle c = new Circle();
Shape s=c;
Circle c1 = (Circle)s;// manual downcasting to circle

Why upcasting is automatic and downcasting is manual because upcasting never fail. If you group of different shapes and want to downcast all of them to circle, then there may be chance, that some of shape are rectangle and code fail by throwing ClassCastException.

Consider this example;
shape s=new shape();
shape s=new circle();

You can store circle as a shape, and you can downcast it to circle when appropriate but doing this might be a sign of bad design.  On the other hand, compiler will let you to cast "s" to a circle, but you'll get a runtime error because the instance isn't actually a circle.

When to Cast Objects
You will have cause to cast objects in both directions through a class hierarchy.

You will cast object in upwards:

• whenever you execute methods polymorphically, you are storing objects in a variable of a base class type and calling methods in a derived class. This generally involves casting the derived class objects to the base class
• You want to cast up through a hierarchy is to pass an object of several possible subclasses to a method. By specifying a parameter as a base class type, you have the flexibility to pass an object of any derived class to it. You could pass a Dog, Duck, or Cat object to a method as an argument for a parameter of type Animal.

You will cast object in downwards:

The reason you might want to cast down through a class hierarchy is to execute a method unique to a particular class. If the Duck class has a method layEgg(), for example, you can't call this using a variable of type Animal, even though it references a Duck object. As I said, casting downward through a class hierarchy always requires an explicit cast.

The object pointed to by aPet is first cast to type Duck. The result of the cast is then used to call the method layEgg(). If the object were not of type Duck, the cast would cause an exception to be thrown.


If you know anyone who has started learning java, why not help them out! Just share this post with them. Thanks for studying today!...

IMP-00037: Character set marker unknown

Solution to IMP-00037: Character set marker unknown problem.


Today while migrating data using imp/exp from oracle 9i to 11g, I faced the following issue
IMP-00037: Character set marker unknown
IMP-00000: Import terminated unsuccessfully

This issue comes into picture when dump (.dmp) file is corrupted.
In my case, it was not the dmp file corruption. I forget to de-compress the file (exp.dmp).

So i used gunzip first to decompress the .dmp file before importing, then I was able import successfully.

Find Next Higher Number With Same Digits

Write a program to find the next highest number by rearranging the digits of a number. For instance, 
If input is 13483 then output must be 13834.

Test cases:
Input     Output
3971     7139
83971   87139
54321   54321
405321 410235


Logic:
Let take a numner 12543 and resulting next higher number is 13245. 
Scan the digits from the tenths digit going towards left (which is 4 in our case) 
At each iteration we check the right digit of the current digit we are at and if the value of the right is greater then current we stop other continue to left 
4>3 continue 
5>4 contine 
2>5 stop 
2 is our pivot element. 
from the digit 2 to the right we find the smallest higher digit of resulting number 2 which 3. 
swap the 3 with 2, it will become 13542. now 3 is our pivot element. 
Now revere the number to right pivot element i.e 3 , it comes 13245 result. 
Note : in case of repeating digit like 147553 we need to swap the 4 with the rightmost digit, otherwise we don't get the highest number. 
Time complexity would be O(n)

Code : 

If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...

PL SQL histogram

Histogram
Histograms are feature in CBO( cost based optimizer ) and it helps to optimizer to determine how data are skewed(distributed) with in the column.Histogram is good to create for the column which are included in the WHERE clause where the column is highly skewed.Histogram helps to optimizer to decide whether to use an index or full-table scan or help the optimizer determine the fastest table join order.

Advantages: 
1. Histograms are useful for Oracle optimizer to choose the right access method in a table.
2. It is also useful for optimizer to decide the correct table join order. When we join multiple tables, histogram helps to minimize the intermediate result set.
 Since the smaller size of the intermediate result set will improve the performance.

Method_opt Parameter: This is the parameter which tells about creating histogram while collecting the statistics. 
The default is FOR ALL COLUMNS SIZE AUTO in Oracle10g. 

We have one table containing 3.6 million record, and one columns emp_status is highly skewed, it two distinct values (N,Y). we have bitmap index on emp_status.

1. Let generate the statistics without any histogram. without histogram oracle assume that data is evenly distributed and optimizer think that we have
1.8 million record for  emp_status=y and 1.8 for emp_status=n

SQL> select count(*),emp_status from pardeep.emp 2 group by emp_status;

COUNT(*) E
---------- -
1 N
3000000 Y

SQL> execute DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'pardeep', TABNAME => 'EMP',ESTIMATE_PERCENT =>10, METHOD_OPT => 'FOR ALL COLUMNS SIZE 1',CASCADE => TRUE);
PL/SQL procedure successfully completed.

SQL> select ename from pardeep.emp where emp_status='Y';
3000000 rows selected.

Examplain plain
Id Operation Name Rows Bytes Cost (%CPU) Time
--------------------------------------------------------------------------
0 SELECT STATEMENT 1832K 15M 5374 (5) 00:01:05
* 1 TABLE ACCESS FULL EMP 1832K 15M 5374 (5) 00:01:05

SQL> select ename from scott.emp where emp_status='N';

Examplain plain
Id Operation Name Rows Bytes Cost (%CPU) Time
--------------------------------------------------------------------------
0 SELECT STATEMENT 1832K 15M 5374 (5) 00:01:05
* 1 TABLE ACCESS FULL EMP 1832K 15M 5374 (5) 00:01:05


Conclusion : Optimizer is using full scan for the query which return 3000000 as well as it using full table scan for query which return only 1 record.

2.  Let us generate the statistics with histogram and see what kind of execution path optimizer is using
FOR COLUMN SIZE 2 EMP_STATUS will create two bucket for column emp_status. 
If we are not sure the distinct number of values in the column, then we can use AUTO option to collect histogram.

SQL> execute DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'pardeep', TABNAME => 'EMP',ESTIMATE_PERCENT =>10, METHOD_OPT => 'FOR COLUMNS SIZE 2 EMP_STATUS',CASCADE => TRUE);

PL/SQL procedure successfully completed.

SQL> select ename from pardeep.emp where emp_status='Y';

3670016 rows selected.

Examplain plain
--------------------------------------------------------------------------
Id Operation Name Rows Bytes Cost (%CPU) Time
--------------------------------------------------------------------------
0 SELECT STATEMENT 3681K 31M 5375 (5) 00:01:05
* 1 TABLE ACCESS FULL EMP 3681K 31M 5375 (5) 00:01:05


SQL> select ename from pardeep.emp where emp_status='N';

Examplain plain
--------------------------------------------------------------------------
Id Operation Name Rows Bytes Cost (%CPU) Time
--------------------------------------------------------------------------
0 SELECT STATEMENT 1 9 1 (0) 00:00:01
1 TABLE ACCESS BY INDEX ROWID EMP 1 9 1 (0) 00:00:01
2 BITMAP CONVERSION TO ROWIDS
* 3 BITMAP INDEX SINGLE VALUE IDX_EMP


Conclusion : Optimizer is using full scan for the query which return 3000000 records. optimizer is using index scan for other query which retrun 1 record.

Data dictionary objects for Histogram: 

• user_histograms
• user_part_histograms
• user_subpart_histograms
• user_tab_histograms
• user_tab_col_statistics

if you find this information useful, please comment.

why static is not allowed in inner class

why static is not allowed in inner class or why static final is allowed in inner class

The idea behind inner classes ( non static inner class) is to operate in the context of the enclosing instance. Somehow, allowing static variables and methods contradicts this motivation.
http://docs.oracle.com/javase/specs/jls/se5.0/html/classes.html#8.1.3

Inner class are like an instance attribute of enclosing object. Also static means to work without instance at first place.
So it's doesn't make sence to allow staic feature in inner classes.

Let take this example:
 class pardeep{
   public String name;
  }

If you create two instance of this pardeep
pardeep a= new pardeep();
a.name="kumar";

pardeep b=new pardeep();
b.name="kumarOne";

It is clear the each has own value for the property name.

The same happens with inner class, each inner class instance is independent of the inner class instance.

So if you try to create counter(static) attribute , there is now way to share the value across two different instances.

class Pardeep {
  public string name;
  class kumar{
    static counter;
  }
}

when you create two instance a and b , what would be the correct value for the static variables counter? It is not possible to determine, because existence of
Kumar class depends completely on each of the enclosing object.
That why static is not allowed in inner.

Note: This is also the reason that when class is declared static, it doesn't need any living instance to live itself.

If this counter is constant, then there will be no problem because value is not going to be changed.
That why final make them(counter) constant once initilazed, is a compile time contant value.
i.e, final static counter;
That why final static is allowed in inner class


If you know anyone who has started learning Java, why not help them out! Just share this post with them.Thanks for studying today!...