Quick Sort

Algorithm :
QUICK SORT (A,p,r)
1 if p < r
2 then q<-- PARTITION(A,p,r)
3 QUICK SORT(A,p,q)
4 QUICK SORT(A,q + 1,r)
Notice that we only examine elements by comparing them to other elements. This makes quicksort a comparison sort. Divide and Conquer Algorithms that solve (conquer) problems by dividing them into smaller sub-problems until the problem is so small that it is trivially solved. in place In place sorting algorithms don't require additional temporary space to store elements as they sort; they use the space originally occupied by the elements. Analysis : The best-case behavior of the quicksort algorithm occurs when in each recursion step the partitioning produces two parts of equal length. In order to sort n elements, in this case the running time is in Θ(n log(n)). This is because the recursion depth is log(n) and on each level there are n elements to be treated (Figure 2 a). The worst case occurs when in each recursion step an unbalanced partitioning is produced, namely that one part consists of only one element and the other part consists of the rest of the elements (Figure 2 c). Then the recursion depth is n-1 and quicksort runs in time Θ(n2). The choice of the comparison element x determines which partition is achieved. Suppose that the first element of the sequence is chosen as comparison element. This would lead to the worst case behavior of the algorithm when the sequence is initially sorted. Therefore, it is better to choose the element in the middle of the sequence as comparison element. Even better would it be to take the n/2-th greatest element of the sequence (the median). Then the optimal partition is achieved. Actually, it is possible to compute the median in linear time [AHU 74]. This variant of quicksort would run in time O(n log(n)) even in the worst case. However, the beauty of quicksort lies in its simplicity. And it turns out that even in its simple form quicksort runs in O(n log(n)) on the average. Moreover, the constant hidden in the O-notation is small. Therefore, we trade this for the (rare) worst case behavior of Θ(n2).

Java Code :

void quicksort(int[] a, int low, int high) {

   if (low > high)
 return;

  int i = low;
  int j = high;
  int h;
  // comparision element
  int x = a[(low + high) / 2];
  // partition
  do {
   while (a[i] < x)
    i++;
   while (a[j] > x)
    j--;
   if (i <= j) {
    h = a[i];
    a[i] = a[j];
    a[j] = h;
    i++;
    j--;
   }
  } while (i <= j);
   quicksort(a, low, j);
   quicksort(a, i, high);
 }

Selection Sort

Refer for animated applets :http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/heapSort/heapSort.html

Algorithm :
for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
→ invariant: a[k] smallest of a[i..n]
swap a[i,k]
→ invariant: a[1..i] in final position
end

java code :

void selectionSort(int[] a) {
int length = a.length;
for (int i = 0; i < length - 1; i++) {
int minPos = i;
for (int j = i + 1; j < length; j++) {
if (a[j] < a[minPos]) {
minPos = j;
}
}
// swapping min element position with i th position
int temp = a[minPos];
a[minPos] = a[i];
a[i] = temp;
}
}

Properties :
Not stable
O(1) extra space
Θ(n2) comparisons
Θ(n) swaps
Not adaptive


Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) comparisons (see arithmetic progression). Each of these scans requires one swap for n − 1 elements (the final element is already in place).


Among simple average-case Θ(n2) algorithms, selection sort almost always outperforms bubble sort and gnome sort, but is generally outperformed by insertion sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.

While selection sort is preferable to insertion sort in terms of number of writes (Θ(n) swaps versus Ο(n2) swaps), it almost always far exceeds (and never beats) the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.

Insertion Sort

java code :

void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int pos = i - 1;
            while (pos >= 0 && a[pos] > key) {
                a[pos + 1] = a[pos];
                pos--;
            }
            a[pos + 1] = key;
        }
    }

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)). 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.
The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time (i.e., O(n2)).
The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quick sort; indeed, good quick sort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.

It is possible to find the inserting position of element ai faster, namely by binary search. However, moving the elements to the right in order to make room for the element to be inserted takes linear time anyway.

Bubble sort

Algorithm

Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
If at least one swap has been done, repeat step 1.
You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops. Let us see an example of sorting an array to make the idea of bubble sort clearer.

java code :

public static void bubbleSort(int[] data)
{
int length = data.length;
for (int k = 0; k < length - 1; k++)
{
boolean isSorted = true;

for (int i = 1; i < length - k; i++)
{
if (data[i] < data[i - 1])
{
int tempVariable = data[i];
data[i] = data[i - 1];
data[i - 1] = tempVariable;

isSorted = false;

}
}

if (isSorted)
break;
}
}


Properties :
Stable
O(1) extra space
O(n2) comparisons and swaps
Adaptive: O(n) when nearly sorted

ArrayList,Linked List and Vector

ArrayList is in most cases what you want to use. It is a list backed by an array, which means it has fast access to each element via the get method.
Vector is a leftover from the early days of Java, retrofitted with the List interface. The chief difference from ArrayList is that its methods are synchronized (ArrayList's are not). That means it is easier to use in multi-threaded environments, but it does incur the synchronization overhead.
LinkedList is backed by a doubly-linked list, not an array. That means it's fast to access elements at the start and the end of the list, but less so in the middle. On the other hand, inserting and deleting elements is fast compared to ArrayList.


An ArrayList is a List implementation backed by a Java array, similar to the Vector class. As the number of elements in the collection increases, the internal array grows to fit them. If there are lots of growth periods, performance degrades as the old array needs to be copied into the new array. However, random access is very quick as it uses an array index to access.
With a LinkedList, the List implementation is backed by a doubly linked list data structure, allowing easy inserts/deletions anywhere in the structure, but really slow random accesses as the access must start at an end to get to the specific position.


A LinkedList is similar to an ArrayList in that it is ordered by index position, but it differs in that the elements are double-linked to one another. This linkage gives you new mehtods for adding and removing from the beginning or end.

If your program frequently provides random access to the data of the list, the ArrayList class offers quick access to individual elements of the list. This quick access comes at a cost of slower operations for adding and removing in the middle of the list. If this latter behavior is what you desire, than the LinkedList class offers a better alternative. It provides quick sequential access, additions, and deletes, at a cost of slower random access.

Run time polymorphism in java

object that it is acting upon. In other words, polymorphism allows you define one interface and have multiple implementation. This is one of the basic principles of object oriented programming.

The method overriding is an example of runtime polymorphism. You can have a method in subclass overrides the method in its super classes with the same name and signature. Java virtual machine determines the proper method to call at the runtime, not at the compile time.

Let's take a look at the following example:

class veicle{
void whoAmI() {
System.out.println("I am a generic veicle.");
}
}
class carextends veicle{
void whoAmI() {
System.out.println("I am a car.");
}
}
class bus extends veicle{
void whoAmI() {
System.out.println("I am a bus.");
}
}

class RuntimePolymorphismDemo {

public static void main(String[] args) {
veicle ref1 = new veicle();
veicle ref2 = new car();
veicle ref3 = new bus();

ref1.whoAmI();
ref2.whoAmI();
ref3.whoAmI();

}
}

The output is

I am a generic veicle.
I am a car.
I am a bus.

String lterals

There are two ways to create a String object in Java:
Using the new operator.
For example,  String str = new String("Hello");.
Using a string literal or constant expression). For example,
String str="Hello"; (string literal) or
String str="Hel" + "lo"; (string constant expression).
What is difference between these String's creations? In Java, the equals method can be considered to perform a deep comparison of the value of an object, whereas the == operator performs a shallow comparison. The equals method compares the content of two objects rather than two objects' references. The == operator with reference types (i.e., Objects) evaluates as true if the references are identical - point to the same object. With value types (i.e., primitives) it evaluates as true if the value is identical. The equals method is to return true if two objects have identical content - however, the equals method in the java.lang.Object class - the default equals method if a class does not override it - returns true only if both references point to the same object.
Let's use the following example to see what difference between these creations of string:
The creation of two strings with the same sequence of letters without the use of the new keyword will create pointers to the same String in the Java String literal pool. The String literal pool is a way Java conserves resources.

public class DemoStringCreation {

 public static void main(String args[]) {
  String str1 = "Hello";
  String str2 = "Hello";
  System.out.println("str1 and str2 are created by using string literal.");
  System.out.println(" str1 == str2 is " + (str1 == str2));// str1 == str2 is true
  System.out.println(" str1.equals(str2) is " + str1.equals(str2));// str1.equals(str2) is true

  String str3 = new String("Hello");
  String str4 = new String("Hello");
  System.out.println("str3 and str4 are created by using new operator.");
  System.out.println(" str3 == str4 is " + (str3 == str4));// str3 == str4 is false
  System.out.println(" str3.equals(str4) is " + str3.equals(str4));// str3.equals(str4) is true

  String str5 = "Hel" + "lo";
  String str6 = "He" + "llo";
  System.out.println("str5 and str6 are created by using string constant expression.");
  System.out.println(" str5 == str6 is " + (str5 == str6));// str5 == str6 is true
  System.out.println(" str5.equals(str6) is " + str5.equals(str6));// str5.equals(str6) is true

  String s = "lo";
  String str7 = "Hel" + s;
  String str8 = "He" + "llo";
  System.out.println("str7 is computed at runtime.");
  System.out.println("str8 is created by using string constant expression.");
  System.out.println(" str7 == str8 is " + (str7 == str8));// str7 == str8 is false
  System.out.println(" str7.equals(str8) is " + str7.equals(str8));// str7.equals(str8) is true
 }
}

String Literal Pool :
String allocation, like all object allocation, proves costly in both time and memory. The JVM performs some trickery while instantiating string literals to increase performance and decrease memory overhead. To cut down the number of String objects created in the JVM, the String class keeps a pool of strings. Each time your code create a string literal, the JVM checks the string literal pool first. If the string already exists in the pool, a reference to the pooled instance returns. If the string does not exist in the pool, a new String object instantiates, then is placed in the pool. Java can make this optimization since strings are immutable and can be shared without fear of data corruption. For example

public class Program {
 public static void main(String[] args) {
  String str1 = "Hello";
  String str2 = "Hello";
  System.out.print(str1 == str2);//true
 }
}

Unfortunately, when you use
String a=new String("Hello");
a String object is created out of the String literal pool, even if an equal string already exists in the pool. Considering all that, avoid new String unless you specifically know that you need it! For example

public class Program {
 public static void main(String[] args) {
  String str1 = "Hello";
  String str2 = new String("Hello");
  System.out.print(str1 == str2 + " ");//false
  System.out.print(str1.equals(str2));//true
 }
}

A JVM has a string pool where it keeps at most one object of any String. String literals always refer to an object in the string pool. String objects created with the new operator do not refer to objects in the string pool but can be made to using String's intern() method. The java.lang.String.intern() returns an interned String, that is, one that has an entry in the global String pool. If the String is not already in the global String pool, then it will be added. For example

public class Program {
 public static void main(String[] args) {
  // Create three strings in three different ways.
  String s1 = "Hello";
  String s2 = new StringBuffer("He").append("llo").toString();
  String s3 = s2.intern();

  // Determine which strings are equivalent using the == operator
  System.out.println("s1 == s2 ? " + (s1 == s2));//s1 == s2? false
  System.out.println("s1 == s3 ? " + (s1 == s3));//s1 == s3? true
 }
}

There is a table always maintaining a single reference to each unique String object in the global string literal pool ever created by an instance of the runtime in order to optimize space. That means that they always have a reference to String objects in string literal pool, therefore, the string objects in the string literal pool not eligible for garbage collection.

String Literals in the Java Language Specification Third Edition
Each string literal is a reference to an instance of class String. String objects have a constant value. String literals-or, more generally, strings that are the values of constant expressions-are "interned" so as to share unique instances, using the method String.intern.
Thus, the test program consisting of the compilation unit:

class Other {
 static String hello = "Hello";
}

class Test {
 public static void main(String[] args) {
  String hello = "Hello", lo = "lo";
  System.out.println((hello == "Hello") + " ");//true
  System.out.println((Other.hello == hello) + " ");//true   
  System.out.println((Other.hello == hello) + " ");//true   
  System.out.println((hello == ("Hel" + "lo")) + " ");//true 
  System.out.println((hello == ("Hel" + lo)) + " ");//false
  System.out.println(hello == ("Hel" + lo).intern()); //true
 }
}

This example illustrates six points:
Literal strings within the same class in the same package represent references to the same String object.
Literal strings within different classes in the same package represent references to the same String object.
Literal strings within different classes in different packages likewise represent references to the same String object.
Strings computed by constant expressions are computed at compile time and then treated as if they were literals.
Strings computed by concatenation at run time are newly created and therefore distinct.
The result of explicitly interning a computed string is the same string as any pre-existing literal string with the same contents.
Refer : http://www.xyzws.com/javafaq/what-is-string-literal-pool/3