Heap Sort Implementation In Java

Heap Sort Implementation In Java

Sorting Techniques

import java.io.*;
 
class heap
{
 public static int c=0;
 public static void main(String args[]) throws IOException
  {
  int a[],n;
   BufferedReader b=new BufferedReader(new InputStreamReader(System.in)); 
   System.out.println("Enter size of array = ");
   n = Integer.parseInt(b.readLine());
   a = new int[n];
   System.out.println("Enter values = ");
   for(int i=0;i<n;i++)
     a[i] = Integer.parseInt(b.readLine());
   heap(a,n);
   System.out.println(" Sorted Array is : ");
   for(int i=0;i<n;i++)
   {
    System.out.println(a[i]+" ");
   }
  }
 
public static void heap(int a[],int n)
{
  int i,s,f,elt,v;
  for(i=1; i<n; i++)
  {
    elt=a[i];
    s=i;
    f=(s-1)/2;
    while(s>0 && a[f]<elt)
    {
      a[s]=a[f];
      s=f;
      f=(s-1)/2;
    }
    a[s]=elt;
   c++;
  }
  for(i=n-1; i>0; i--)
  {
    v=a[i];
    a[i]=a[0];
    f=0;
    if(i==1)
    s=-1;
    else
    s=1;
    if(i>2 && a[2]>a[1])
    s=2;
    while(s>=0 && v<a[s])
    {
      a[f]=a[s];
      f=s;
      s=2*f+1;
      if((s+1)<=i-1 && a[s]<a[s+1])
     s=s+1;
      if(s>(i-1))
     s=-1;
     }
     a[f]=v;
    }
}
}

You Might Also Like :