Java Code House

The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input array A[1 : : n ],where n=A:length. Since the maximum element of the array is stored at the root A[1] , we can put it into its correct final osition by exchanging it with A[n] . If we now discard node n from the heap - and we can do so by simply decrementing A:heap-size-- we observe that the children of the root remain max-heaps, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property, however, is call MAX-HEAPIFY(A, 1), which leaves a max-heap in A[1 : : n -1] . The heapsort algorithm then repeats this process for the max-heap of size n- 1 down to a heap of size 2.
     The program written below has build_max_heap() to build the max-heap, max_heapify() to retain the max-heap property and heap_sort() for sorting. The most important thing of the code is that you can use this to sort anything. Just pass an array of any object which is comparable i.e. implements Comparable interface or any array of wrapper class objects like Integer, Float etc. This is only beacause we have done this using Java's generics feature to make this code generic and general and no need for different implementations.

Heapsort operation

--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------

import java.util.Scanner;

/*This code can take in any array of Comparable i.e whose data can be compared and generates the sorted elements using heap sort*/
public class HeapSort<E extends Comparable<? super E>>{
    private int heap_size;
private E A[];

public HeapSort(E a[]){
  A=a;
}

private void build_max_heap(){  //building max-heap
   heap_size=A.length-1;
   for(int i=heap_size/2;i>=0;i--)
  max_heapify(i);
}

private void swap(int i,int j){
   E tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}

private void max_heapify(int i){
   int l=2*i,r=2*i+1;  //left and right child
int largest;
   if(l<=heap_size && A[l].compareTo(A[i])>0)
  largest=l;
else largest=i;
if(r<=heap_size && A[r].compareTo(A[largest])>0)
  largest=r;
if(largest!=i){    //finding largest, swapping and then reheapify
  swap(i,largest);
  max_heapify(largest);
}
}

public E[] heap_sort(){
   build_max_heap();
for(int i=A.length-1;i>=0;i--){
  swap(0,i);  //swapping with first
  heap_size--;  //decreasing size
  max_heapify(0);  //reheapify
}

return A;
}

public static void main(String[] args)throws Exception{
Scanner sc=new Scanner(System.in);
System.out.print("Enter size : ");
int n=sc.nextInt();
Integer a[]=new Integer[n];
System.out.println("Enter elements to be sorted -->");
for(int i=0;i<n;i++)
  a[i]=sc.nextInt();
  
HeapSort<Integer> obj=new HeapSort<Integer>(a);
a=obj.heap_sort();
System.out.println("Sorted array -->");
for(int i=0;i<n;i++)
  System.out.print(a[i]+"  ");
    }
}

Radix Sort is a type of bucket sort. This type of sort is based on radix i.e. 10 for decimal numbers and 26 for alphabets. This technique is very useful in sorting words alphabetically. Arrays are sorted in a total of "d" passes where "d" is the number of digits of highest number..
For decimal numbers : In first pass array is sorted according to units digit , then in next pass sorted according to tens digit and so on.This process goes on till all the digits of highest numbers are traversed.
For words : In first pass array is sorted according to first letter , and in second pass second character is considered and so on.
Here is the code for you -->

import java.io.*;
public class Radix_Sort {

    public void sort(int a[],int rad,int max){
        int tmp[][]=new int[a.length][10];

        for(int i=0;i<max;i++){

            int c=0;
            for (int j=0;j<a.length;j++)
                for(int k=0;k<rad;k++)
                    tmp[j][k]=0;

            for(int k=0;k<a.length;k++){
                int d=(int)((a[k]/Math.pow(10,i))%10);
                tmp[k][d]=a[k];
            }

            for (int j=0;j<rad;j++)
                for(int k=0;k<a.length;k++)
                    if(tmp[k][j]!=0)
                        a[c++]=tmp[k][j];
        }

        disp(a);
    }

    public void input()throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Enter array size : ");
        int n=Integer.parseInt(br.readLine());
        int a[]=new int[n];
        System.out.println("Enter elements in array ------->");
        int max=0;
        for (int i = 0; i<n; i++) {
            System.out.print("Enter number : ");
            a[i]=Integer.parseInt(br.readLine());
            if(a[i]>max)
                max=a[i];
        }
        sort(a,10,digit_count(max));
     }

    int digit_count(int n){
        int d=0;
        while (n!=0) {
            d++;
            n/=10;
        }
        return d;
    }

    public void disp(int a[]){
        System.out.println("\nArray after sorting -------->");
        for (int i = 0; i<a.length; i++)
            System.out.print(a[i]+"  ");
    }

    public static void main(String[] args) throws Exception{
        new Radix_Sort().input();
    }
}

You can also download the source from below links :
DOWNLOAD source JAVA file from MediaFire
DOWNLOAD the JAVA file from 4shared