Counting sort in java

Any sorting technique which includes comparison of elements requires at least Ω(n logn) time if no extra space is used.
To sort an array in linear time that is O(n) we need extra space.

Counting sort can be used to sort an array in linear time while using some extra space.
But there are few assumptions while sorting using counting sort:
1. Array A is input array, Array B is output(sorted array), Array C is auxiliary space(C[0..k])
2. Array A contains elements in the range of 0..k where k is max element, so we need auxiliary array C with space[0..k]
3. Hence complexity becomes O(n+k).

Following program implements Counting sort in java.

/**
 * @author vikky.agrawal
 *
 */
public class CountingSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
         CountingSort obj=new  CountingSort();
         int a[]=new int[]{7,2,6,9,1,2,8,0,5,4,2,3,1,6};
         obj.countingSort(a, 9);
        
    }
    
/**
 * Algorithm
 * COUNTING-SORT.(A;B;k)
 * A[1...n] input array
 * B[1...n] output array
 * C[0...k] auxiliary array(k is the max element)
 * 
 * 1 let C[0..k]be a new array
 * 2 for i =0 to k
 * 3 C[i]=0;
 * 4 for j=1 to A.length
 * 5 C[ A[j] ]=C[ A[j] ]+1;
 * 6 // C[i]now contains the number of elements equal to i.
 * 7 for i= 1 to k
 * 8 C[i]=C[i]+c[i-1];
 * 9 //C[i] now contains the number of elements less than or equal to i.
 * 10 for j= A.length down to 1
 * 11 B[C[A[j]]]=A[j];
 * 12 C[A[j]]=C[A[j]]-1;
*/
    
    /**
     * Sorting in linear time with auxiliary space O(n+k)
     */
    public int[] countingSort(int[] a,int k){
        
        
        System.out.println("Input array :");
        printArray(a);
        
        int[] b=new int[a.length];
        int[] c=new int[k+1];
        
        for(int i=0; i < a.length;i++){
            c[a[i]]=c[a[i]]+1;
        }
        // C[i] now contains the number of elements equal to i. if c[5]=3 then there are 3 5's
        
        
        //sutract 1 to make array index from 0;
        c[0]=c[0]-1;
        for(int i=1; i < c.length;i++){
            c[i]=c[i]+c[i-1];
        }
        
        //C[i] now contains the number of elements less than or equal to i.
        //if c[1]=3 then there are 3 elements which are less than or equal to 1. 
        
        for(int j=a.length-1; j&gt;=0 ;j--){
            b [ c[a[j] ]]=a[j];     //c[j] contains actual location of a[j]; 
            c[a[j]]=c[a[j]]-1;
        }
        
        System.out.println("\nSorted array :");
        printArray(b);        
        
        return b;
    }
    
    public void printArray(int[] arr){
        for (int a : arr) {
            System.out.print(a + " ");
        }    
        System.out.println();
    }

}

Complexity analysis of counting sort:
Since there is no comparison involved in counting sort, there are no inner loops.
So a total running time of O(n) is required for input array and O(k) time required for auxiliary array.
Total running time could be estimated by O(n+k); which is a linear function hence counting sort runs in linear time.

Heap sort in java

Here I am taking example of MaxHeap, a minheap can be implemented and sorted in the same way after some modifications. So wherever a heap mentioned in this post it will refer to MaxHeap.

Heap property:In a Heap data structure left and right node contains value less than the parent node.
for any indice i
leftchild  : 2i + 1
rightchild : 2i + 2
parent     : floor((i − 1)/2

To build a heap we use heapify function which runs in O(logn) time, and total time taken to build a heap happens to be O(n).

To sort a heap, we remove the root node which must be maximum, and add it at the end of array. After that we use heapify function on the array but ignoring index at which this element is added.
Repeating this process for 0 to array.length sorts array.

Following program implements Heap sort in java.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

/**
 * @author vikky.agrawal
 * 
 */
public class HeapSort {

    
    ArrayList<Integer> array;

    HeapSort() {
        array = new ArrayList<Integer>();
    }
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        new HeapSort().operate();
    }

    public void operate(){
        for (int i = 0; i < 11; i++) {
            array.add(((int) (Math.random() * 100)));
        }

        System.out.println("Array before maxheapify :");
        printArray();
        
        buildMaxHeap();
        
        System.out.println("Array after max heapify");
        printArray();
        
        this.heapSort();        
        
        System.out.println("\nArray after Heap Sort");
        
        printArray();
        System.out.println("\nIs Array sorted now ? " +isSorted());
    }
    
    /**
     * Heapify takes O(log n) / O(height)
     */

    public void heapify(ArrayList<Integer> array, int index,int size) {
        
            
        int left = this.getLeft(index);
        int right = this.getRight(index);

        int largest = array.get(index);
        int temp = index;

        if (left != -1 && array.get(left) > largest && left<size) {
            largest = array.get(left);
            temp = left;
        }

        if (right != -1 && array.get(right) > largest && right <size) {
            largest = array.get(right);
            temp = right;
        }
        
        if (temp != index) {
            int tempo = array.get(index);
            array.add(index, array.get(temp));
            array.remove(index+1);
            array.add(temp, tempo);
            array.remove(temp+1);
        
            if(temp < size / 2){
                heapify(array,temp,size);
            }
        }
        
    }

    /**
     * Building a Max Heap takes O(n) time
     */
    public void buildMaxHeap() {
        int size=array.size();
        for (int i = ( size / 2)-1; i >= 0; i--) {
             this.heapify(array, i,size);
        }
    }
    
    /**
     * Heap sort takes O(n logn) overall;
     */
    public void heapSort(){
        
        int size=array.size();
        int index=size-1;
        
        for (int i = 0 ; i <size; i++) {    
            int data=array.remove(0);
            array.add(index, data);                    
            
            for (int j = ( size / 2)-1; j >= 0; j--) {
                 this.heapify(array, j,index);
            }
            index--;             
        }
        
        //Reverse the array for sorted version (runs in linear time)
        Collections.reverse(array);
    }
    
    /**
     * Helper functions for Heap
     */
    public int getLeft(int index) {
        if ((index * 2) + 1 < array.size()) {
            return (index * 2) + 1;
        } else {
            return -1;
        }
    }

    public int getRight(int index) {
        if ((index * 2) + 2 < array.size()) {
            return (index * 2) + 2;
        } else {
            return -1;
        }
    }

    public int getParent(int index) {
        if (index < array.size()) {
            if (index % 2 == 0) {
                return (index / 2) - 1;
            } else {
                return index / 2;
            }
        } else
            return -1;
    }

    public void printArray(){
        Iterator<Integer> itr = array.iterator();
        while (itr.hasNext()) {
            System.out.print(itr.next() + " ");
        }
        System.out.println();
    }
    
    public boolean isSorted(){
        
        for(int i=1;i<array.size();i++){
            if(array.get(i) > array.get(i-1)){
                return false;
            }
        }
        return true;
    }

}

Complexity analysis:
Complexity of Heap sort is O(n logn)
To build a heap it takes time: O(n), and for each element we call heapify function which takes O(logn), hence total time taken to sort the array will be: O(n logn).

Facts:
1. Heap sort is not a stable sort(order of same elements in sorted array might change)
2. Merge Sort requires Ω(n) auxiliary space(for merging), but heapsort requires only a constant space.
3. Heapsort typically runs faster in practice on machines with small or slow data caches.

Quick Sort in Java

Quick sort works on the principle of divide and conquer.
Divide the list in 2 sub-lists, find a pivot element such that its actual position divides the list further in 2 lists.
So the pivot element resides at its actual position and then recursively find location of other elements. At the end of processing each element will get its actual(sorted) position and array will be sorted.

Algorithm QuickSort: 
1. QuickSort(Arr, p, r) 
2. if(p < r) 
3. q=findPivot(Arr,p,r); //find pivot and its location [ takes O(n) ] 
4. QuickSort(Arr, p,q-1); //left sub array 
5. QuickSort(Arr, q+1,r); // right sub array Algorithm for partition to find pivot 

Algorithm for partition to find pivot :
 PARTITION (Arr, p, r )
 1. x =A[r]
 2. i = p-1
 3. for j =p to r-1
 4.    if A[j] <= x
 5.     i=i+1
 6.    exchange A[i]  with A[j]
 7. exchange A[i+1] with x
 8. return i+1

Following program implements Quick sort in java.

/**
 * @author vikky.agrawal
 *
 */
public class QuickSort {

 
 int[] arr;
 
 QuickSort(){
  arr=new int[] { 5, 3, 1, 2, 9, 8 };
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  
  QuickSort obj = new QuickSort();
  obj.operate();
 }
 
 
 public void operate(){
  
  System.out.println("Array before sortings: ");
  printArray();
  quickSort(arr,0,5);

  System.out.println("Sorted array : ");
  printArray();
 }
 
 
 public void quickSort(int[] arr, int p, int r){
  
  if(p<r){
   int q= findPivot(arr,p,r);
   quickSort(arr, p, q-1);
   quickSort(arr, q+1, r);
  }
  
 }
 
 
 /**
  * Algorithm for partition to find pivot
  * 
  * PARTITION.A;p;r
  * 1 x =A[r]
  * 2 i = p-1
  * 3 for j =p to r-1
  * 4   if A[j] <= x 
  * 5   i=i+1 
  * 6   exchange A[i]  with A[j]
  * 7 exchange A[i+1] with x 
  * 8 return i+1
  */
 
 public int findPivot(int[] arr, int p, int r){
  
  int x=arr[r];
  int i=p-1; 
  
  for(int j=p ;j<r; j++){
   if(arr[j]<= x){
    i++;
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
   }
  }  
  
  arr[r]=arr[i+1];
  arr[i+1]=x;
  return i+1;
 }
 
 public void printArray(){
  for (int a : arr) {
   System.out.print(a + " ");
  }
  System.out.println();
 }
}

Complexity analysis:
In average case scenario each problem is divided in 2 sub problems, hence total time required will be:
T(n)= 2T(n/2)+O(n) where O(n) is to find pivot and its location.
Using Master theorem solution to above equation comes as O(n logn)(Avg case)
In worst case scenario array may be divided in (1, n-2) in that case total time required will be
 T(n)= T(1)+T(n-2)+O(n) and solution to this equation becomes : O(n^2) (Worst case)

 But worst case is rare in quick sort and analysis shows that mostly average case occurs with complexity O(n logn).
For more analysis check wiki: Quicksort#analysis  

Facts:
1. Worst case for quick sort occurs when array is already sorted.
2. Worst case also occurs when all the elements are same.

3. Quick sort gives better results than Mergesort in average case.

Merge Sort in Java

Merge sort works on the principle of divide and conquer.
Divide the list in 2 sub-lists, and repeat until there is only 1 element, a sub-list with single element is already sorted.
Now merge the sorted sub-lists to get a sorted list until there is only a single sorted list.

Algorithm:
1. MergeSort(Arr, p ,r)
2. if(p < r)
3.  q=[p+r/2];
4.  MergeSort(Arr, p,q);    //left sub array
5.  MergeSort(Arr, q+1,r);  // right sub array
6.  Merge(Arr, p , q, r);   //Merge, sorted sub arrays [takes O(n) ]

Following program implements Merge sort in java.

/**
 * @author Vikky.Agrawal
 *
 */
public class MergeSort {

 
 int[] arr;
 
 MergeSort(){
  arr=new int[] { 5, 3, 1, 2, 9, 8 };
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {

  MergeSort obj = new MergeSort();
  obj.operate();
 }
 
 
 public void operate(){
  System.out.println("Array before sortings: ");
  printArray();
  mergeSort(arr,0,5);

  System.out.println("Sorted array : ");
  printArray();
 }
 
 
 public void mergeSort(int[] arr, int p, int r){
  if(p<r){
   int q=(p+r)/2;
   mergeSort(arr, p, q);
   mergeSort(arr, q+1, r);
   merge(arr,p,q,r);
  }
 }
 
 public void merge(int[] arr, int p, int q, int r){
  
  int length=arr.length;
  int[] tempArray =new int[length];

  for (int i=0;i<length; i++) {
   tempArray[i]=arr[i];
  }
  
  int temp=p;
  int i=p,j=q+1;
  for(; i<=q && j<=r ; ){
   if(tempArray[i] < tempArray[j]){
    arr[temp++]=tempArray[i];
    i++;
   }else{
    arr[temp++]=tempArray[j];
    j++;
   }
  }
  
  while(i <= q){
   arr[temp++]=tempArray[i];
   i++;
  }
  
  while(j < r){
   arr[temp++]=tempArray[j];
   j++;
  }
 }
 

 public void printArray(){
  for (int a : arr) {
   System.out.print(a + " ");
  }
  System.out.println();
 }

}

Complexity analysis:
Since each problem is divided in 2 sub problems and then these sub problems merged.
Total time required will be T(n)= 2T(n/2)+O(n)
where O(n) is to merge sub problems.
Using Master theorem #case2 solution to above equation comes as O(n logn).

In worst case scenario Merge sort beats Quick sort which requires O(n^2)
worst case time.

For more analysis follow wikipedia: Merge_sort#Analysis
In the worst case, the number of comparisons merge sort makes is equal to or slightly smaller than (n logn - 2 logn + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n))

Master theorem for complexity analysis

Master theorem is used to analyze complexity of many problems in divide and conquer category.
Master theorem deals with recurrence relations in the form:

T(n)= aT(n/b)+f(n)
where:
n is size of original problem
a is number of sub-problems
n/b size of sub-problems(assuming sub-problems of equal size)

f(n) is the time required to conquer(dividing or merging) the sub-problems;

such as merging in merge sort or finding pivot in quick sort</em>

There are 3 cases to solve such kind of recurrences:
In each of three cases we compare f(n) with (n ^log_ba). Polynomially larger of these functions determines solution.

Case 1:
If f(n) = O( n^c ) where c < log_ba
then solution becomes T(n) = θ(n ^log_ba)

In first case, comparison states that (n ^log_ba) is larger than f(n),hence solution θ(n ^log_ba)

For example:
T(n) = 9T(n/3)+1000n²
a=9, b=3, f(n)=n² (leaving constant terms)
n ^log_ba = n ^log₃9 = n³ which is polynomially greater than n².
Hence solution T(n) = θ(n³)

Case 2:
 if f(n) = θ(n ^{log _b a} )
then solution becomes T(n) = θ(n ^log_ba logn)
In second case, comparison states that (n ^log_ba) is equal to f(n), we multiply f(n) by logarithmic factor hence solution θ(n ^log_ba logn)

For example:
T(n) = T(n/2)+c (Binary search)
a=1, b=2, f(n)=c (constant)
n ^log_ba = n ^log₂1 = n⁰ = 1 which is equal to f(n).
Hence solution T(n) = θ(logn)

Case 3:
if f(n) = Ω( n^c ) where c > log_ba
and it is also true that af(n/b) <= kf(n) for some constant k < 1,
and sufficiently large n.
then solution becomes T(n) = θ( f(n) )

In third case comparison states that (n ^log_ba) is smaller than f(n).
hence solution θ( f(n) )

For example:
T(n) = 2T(n/2)+10n² a=2, b=2, f(n)=n² (leaving constant terms)
n ^log_ba = n ^log₂2 = n which is polynomially smaller than n².
Hence solution T(n) = θ(n²)  

Facts :
Master theorem doesn't apply if function is not polynomially large enough to determine solution.
 eg : T(n) = 2T(n/2)+nlogn here a=2,b=2
f(n) = n logn;
n^log_ba = n;
so f(n) is greater than n^log_ba but not polynomially large enough, its large by a factor of logarithm hence can't determine solution.

Insertion Sort in java

Insertion sort takes the input array and sorts it, all the elements in the array before the loop invariant (loop variable) are sorted. Hence we start our loop from index 1 and iterate.(Assuming that first element is sorted) While looping current item is compared with sorted array and its actual index identified, after loop completion it is inserted at its actual location.
Following program implements Insertion sort in java.

/**
 * @author vikky.agrawal
 * 
 */
public class InsertionSort {

	
	int[] arr;
	
	InsertionSort(){
		arr=new int[] { 5, 3, 1, 2, 9, 8 };
	}
	
	/**
	 * @param args
	 */
	
	public static void main(String[] args) {

		InsertionSort obj = new InsertionSort();
		obj.operate();
	}
	
	public void operate(){

		System.out.println("Array before sortings: ");
		printArray();
		sort();

		System.out.println("Sorted array : ");
		printArray();
	}
	

	/**
	 * Insertion Sort algo: 
	 * 1 for j=1 to Arr.length 
	 * 2 key= Arr[j]; 
	 * 3 //Insert Arr[j] into the sorted sequence Arr[0...j-1].
	 * 4 i=j-1; //initialization for looping 
	 * 5 while (i>=0 and Arr[i] >key) 
	 * 6   Arr[i+1]=Arr[i] 
	 * 7   i=i-1; 
	 * 8 Arr[i+1] = key
	 */

	public int[] sort() {

		int length = arr.length;
		int i = 0;
		int key = 0;
		for (int j = 1; j < length; j++) {
			i = j - 1;
			key = arr[j];
			while (i >= 0 && arr[i] > key) {
				arr[i + 1] = arr[i];
				i--;
			}
			arr[i + 1] = key;
		}

		return arr;
	}

	public void printArray(){
		for (int a : arr) {
			System.out.print(a + " ");
		}
		System.out.println();
	}
}

Complexity analysis of Insertion sort :
Outer loop runs for n-1 times.In the worst case the inner while loop will execute for each element and hence will sum up as:
(∑ tj-1 where j=2 to n) = 1+2+3+4+-------+n-1 = n*(n-1)/2 = n^2.
Hence to sum up the overall complexity worst case time required in insertion sort will be equal to O(n^2).

When to use insertion sort / Characteristics of Insertion sort
1. Insertion sort should be used when data is nearly sorted, in such cases inner while loop won't get executed and performance of insertion sort remains better than its worst case.
2. Insertion sort could be used when data size is smaller, as it requires little/no overhead.
3. It's stable sort (i.e. does not change the relative order of elements with equal values after sorting)
4. In-place sorting- requires constant amount of extra space.

Rotate a linked list anti clock wise for given number of nodes

Java program to rotate a given Linked list anti clockwise for given no of nodes.

/**
 * @author vikky.agrawal
  */

public class LinkedList {

	Node node = null;	

	public static void main(String[] args) {

		LinkedList list = new LinkedList();
		list.operations();

	}

	public void operations() {

		this.node = new Node(10);

		for (int i = 1; i < 6; i++) {
			add(node, (int) (Math.random() * 100));
		}
		this.rotateACW(node, 8);
	}
	
	/**
	 * Rotate a linked list Anti clock wise for given number of nodes
	 */

	public void rotateACW(Node root, int n) {

		if (root == null || n<=0) {
			return;
		}

		int size=size(root);
		if(n==size){
			//no need to rotate, as it will be the same
			System.out.println("List after rotating");
			print(root);
			return;			
		}
		
		if (n > size) {
			n=n%size;
		}

		System.out.println("List Before rotating");
		print(root);

		Node ptr = root;
		Node ptr1 = null;

		while (n-- > 0) {
			ptr1 = ptr;
			ptr = ptr.getLink();
		}

		Node temp = ptr;

		while (temp.getLink() != null) {
			temp = temp.getLink();
		}

		temp.setLink(root);
		ptr1.setLink(null);
		root = ptr;

		System.out.println("List after rotating");
		print(root);

	}
	
	
	/**
	 * Helper functions for LinkedList
	 */
	public void add(Node ptr, int data) {
		if (ptr == null) {
			System.out.println("Always null ?");
			ptr = new Node(data);
		} else {
			Node newptr = ptr;
			while (newptr.getLink() != null) {
				newptr = newptr.getLink();
			}
			newptr.setLink(new Node(data));
			newptr.getLink().setLink(null);
		}
	}

	public void print(Node ptr) {

		if (ptr == null) {
			return;
		}
		Node ptr1 = ptr;
		System.out.print(ptr1.getData() + "->");
		while ((ptr1 = ptr1.getLink()) != null) {
			System.out.print(ptr1.getData() + "->");
		}
		System.out.println("/n");

	}

	public int size(Node ptr) {

		if (ptr == null) {
			return -1;
		}
		Node ptr1 = ptr;
		int i = 1;
		while ((ptr1 = ptr1.getLink()) != null) {
			i++;
		}
		return i;
	}
	
	/**
	 * static inner class for LinkedList Data Structure
	 */
	private static class Node{
		 private int data;
		 private Node link; 		 
		    
		    Node(){
		    	    	
		    }
		    
		    Node(int data){
		    	//mergedList=new Node();
		        this.setData(data);
		        this.setLink(null);       
		    }
		    
		    public int getData(){
		        return this.data;
		    }
		      
		    public Node getLink(){
		        return this.link;
		    }
		    
		    public void setData(int data){
		        this.data=data;
		    }       
		    
		    public void setLink(Node link){
		        this.link=link;
		    }  
	}
	
}