korayucar
7/7/2016 - 8:02 AM

Heapsort implementation and some benchmark code. This implementation is considerably slower that mergesort or quicksort..

Heapsort implementation and some benchmark code. This implementation is considerably slower that mergesort or quicksort..

public class HeapSort {
    
    public static void sort(int[] arr){
        int heapSize = arr.length;
        heapConstruct(arr, heapSize);
        while(heapSize > 0 ){
            swap(arr, heapSize -1 , 0);
            heapSize--;
            heapify(arr, 0 , heapSize);
        }
    }
    
    private static void heapConstruct(int[] arr ,int heapSize){
        for(int i = heapSize/2; i >=0 ; i--)
            heapify(arr,i,heapSize);
    }
    
    private static void heapify (int [] arr , int index, int heapSize) {
        int maxIndex = index;
        int left = left(index);
        int right = right (index);
        if(left < heapSize && arr[index] < arr[left] )
            maxIndex  = left;
        if(right < heapSize && arr[maxIndex] < arr[right] )
            maxIndex  = right;
        if(maxIndex != index){
            swap(arr,index , maxIndex);
            heapify(arr,maxIndex ,heapSize);
        }
        
        
    }
    
    private static int left(int i){return 2*i+1;}
    private static int right(int i){return 2*i+2;}
    private static int parent(int i){return i/2;}
    
    private static void swap ( int [] arr , int i , int j){
        int dummy = arr[i];
        arr[i] = arr[j];
        arr[j] = dummy;
    }
    
    /** picks the medium element to partition around and puts it to end index */
    private static void pickMediumElement(int arr[] , int start , int end){
    }
    
    static Runtime instance = Runtime.getRuntime();
    static int mb = 1024 * 1024;
    public static void main(String... args){
        Random r = new Random();
          
         
        
     
        for(int j = 1 ; j < 100000002 ; j*=10) {
            System.out.println();
            
            System.gc();
            System.out.println("Used Memory after gc: "
                    + (instance.totalMemory() - instance.freeMemory()) / mb);
            int[] arr = new int[j];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt();
            }
            System.out.println("Used Memory after array creation: "
                    + (instance.totalMemory() - instance.freeMemory()) / mb);
            long startTime = System.nanoTime();
            HeapSort.sort(arr);
            long endTime = System.nanoTime();
            System.out.println("Used Memory after sort: "
                    + (instance.totalMemory() - instance.freeMemory()) / mb);
            System.out.println("time passed : " +(endTime - startTime)/1000+" μs");
            for (int i = 1; i < arr.length; i++) {
                if(arr[i] < arr[i-1] )
                    throw new IllegalStateException("sort failed");
            }
        }
    }
    
}