Jumat, 22 Juni 2012

SOURCE CODE HEAP SORT


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package sorting;

/**
 *
 * @author Acer
 */

    /**
 * For any element, i, in a list of size n, the following is true:
 *    -Parent element index = i/2 (floor(i))
 *    -Left child element index = 2i
 *    -Right child element index = 2i + 1
 */

import java.util.*;
import java.lang.*;


public class heapsort {
    private static int count;
    private static int search;
    public static void main(String a[]) {
        int i;
        int arr[] = {20, 29, 7, 3, 31, 2, 5, 11, 9, 17};
        System.out.println("Unsorted Array\n---------------");
        for (i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
        for (i = arr.length; i > 1; i--) {
            HeapSort(arr, i - 1);
        }
        System.out.println("\nSorted array\n---------------");
        for (i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println("\n");
        System.out.println("Data sorted after " + count + " times swapping");
        System.out.println("Data sorted after " + search + " searching");
    }
    public static int HeapSort(int array[], int arr_ubound) {
        int i, j;
        int lChild, rChild, mChild, root, temp;
        root = (arr_ubound - 1) / 2;
        for (j = root; j >= 0; j--) {
            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;
                }
            }
            count++;
        }
        search++;
        temp = array[0];
        array[0] = array[arr_ubound];
        array[arr_ubound] = temp;
        return count;
    }
}

Tidak ada komentar:

Poskan Komentar