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.