Algorithm - Heap Sort

Heap Sort
Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

It's an In-Place algorithm, but It's not a stable sort.

Solution

public class HeapSort {
    private static int num;
    public static void sort(int array[]) {
        doSort(array);
        for (int i = num; i > 0; i--) {
            swap(array, 0, i);
            num = num - 1;
            maxHeap(array, 0);
        }
    }
    public static void doSort(int arr[]) {
        num = arr.length - 1;
        for (int i = num / 2; i >= 0; i--) {
            maxHeap(arr, i);
        }
    }
    public static void maxHeap(int array[], int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int max = i;
        if (left <= num && array[left] > array[i]) {
            max = left;
        }
        if (right <= num && array[right] > array[max]) {
            max = right;
        }

        if (max != i) {
            swap(array, i, max);
            maxHeap(array, max);
        }
    }
    public static void swap(int array[], int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int array[] = {11, 8, 34, 5, -4, 19, 0, 25, 97, 83, 20};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            if (i > 0) {
                System.out.print(", ");
            }
            System.out.print(array[i]);
        }
    }
}

Result:
-4, 0, 5, 8, 11, 19, 20, 25, 34, 83, 97

Finally, Which sort is best?
Quick Sort is generally considered to be the best sorting algorithm. Compare from other sorting techniques, quick sort is much better than others.


Reason
Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.

To Know more sorting algorithms, just visit WIKIPEDIA

Comments

Popular posts from this blog

Clear the app data programmatically in android

Speed up gradle build in Android Studio.

Proguard usage in Android