Heap Sort using Java

Here's another sorting algorithm called Heap sort.Its a little bit tougher than the remaining sort to implement .But we assure you that TJ would provide you with the most simplified programs.Let's consider an example first then we would move to the program.




Program For Heap Sort Using Java

/**
 *
 * @author The Cyber Soul
 */import java.io.*;
public class HeapSort{
  public static void main(String a[]) throws IOException{
  int i,n;
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  System.out.println("How many elements do you want to sort");
  n=Integer.parseInt(br.readLine());
  int arr[] =new int[n];
  System.out.println("Enter the values to be sorted");
  for(i=0;i<n;i++)
  {
    arr[i]=Integer.parseInt(br.readLine());
  }
  System.out.println("\n  Heap Sort\n---------------\n");
  System.out.println("\n  Unsorted Array\n\n");
  for (i = 0; i < arr.length; i++)
  System.out.print(" "+arr[i]);
  for(i=arr.length; i>1; i--){
  fnSortHeap(arr, i - 1);
  }
  System.out.println("\n  Sorted array\n---------------\n");
  for (i = 0; i < arr.length; i++)
  System.out.print(" "+arr[i]);
  }

  public static void fnSortHeap(int array[], int arr_ubound){
  int i, o;
  int lChild, rChild, mChild, root, temp;
  root = (arr_ubound-1)/2;

  for(o = root; o >= 0; o--){
  for(i=root;i>=0;i--){
  lChild = (2*i)+1;
  rChild = (2*i)+2;
  if((lChild <= arr_ubound) && (rChild <= arr_ubound)){
  if(array[rChild] >= array[lChild])
  mChild = rChild;
  else
  mChild = lChild;
  }
  else{
  if(rChild > arr_ubound)
  mChild = lChild;
  else
  mChild = rChild;
  }

  if(array[i] < array[mChild]){
  temp = array[i];
  array[i] = array[mChild];
  array[mChild] = temp;
  }
  }
  }
  temp = array[0];
  array[0] = array[arr_ubound];
  array[arr_ubound] = temp;
  return;
  }
}