Sorting in Java- Take II

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(nlog n) runtime.
The heapsort algorithm can be divided into two parts.
In the first step, a heap is built out of the data.
In the second step, a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array. The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by choosing a min-heap or max-heap in step one.
A java approach to Heap Sort


package Sorting;
// Heap Sort program
public class HeapSort
{
 private static int[] a;
 private static int n;
 private static int left;
 private static int right;
 private static int largest;
 public static void buildheap(int []a){
 n=a.length-1;
 for(int i=n/2;i>=0;i--){
 maxheap(a,i);
 }
 }

 public static void maxheap(int[] a, int i){
 left=2*i;
 right=2*i+1;
 if(left <= n && a[left] > a[i]){
 largest=left;
 }
 else{
 largest=i;
 }

 if(right <= n && a[right] > a[largest]){
 largest=right;
 }
 if(largest!=i){
 exchange(i,largest);
 maxheap(a, largest);
 }
 }

 public static void exchange(int i, int j){
 int t=a[i];
 a[i]=a[j];
 a[j]=t;
 }

 public static void sort(int []a0){
 a=a0;
 buildheap(a);

 for(int i=n;i>0;i--){
 exchange(0, i);
 n=n-1;
 maxheap(a, 0);
 }
 }

 public static void main(String[] args) {
 int []a1={4,1,3,2,16,9,10,14,8,7};
 sort(a1);
 for(int i=0;i<a1.length;i++){
 System.out.print(a1[i] + " ");
 }
 }
}

 

Advertisements