Skip to main content

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

Clear the App Data Programmatically in Android

Application data has been created due to use shared preference data, databases and network caches data. This data has been manually clear on Settings -- > Apps (or) Application Manager --> Select the app you want to clear the data. --> Then click button clear data to erase the app from the Phone and SDCARD.

Applications like facebook, google+, gmail and some games captures more data on phone and SDCARD.

Once you clear the data of your app, all passwords and saved settings in app has been lost. So carefull to use this method.

Create the Class MyApplication

public class MyApplication extends Application {
 private static MyApplication instance;
 @Override
 public void onCreate() {
  super.onCreate();
  instance = this;
 }
 public static MyApplication getInstance(){
  return instance;
 }
 public void clearApplicationData() {
  File cache = getCacheDir();
  File appDir = new File(cache.getParent());
  if(appDir.exists()){
   String[] children = app…

Sort the numbers using If, Else and Loop.

This is very interesting. You need to sort the numbers, but not using the SORT functions. You can use the If, Else or Loop to do the functions.

See the solution:

import java.util.Scanner;
public class OrderNumbers {
    public static void main(String[] args) {         Scanner in = new Scanner(System.in);         System.out.println("Enter the size of an Array");         int num = in.nextInt();         int [] numbers = new int[num];         for (int i = 0; i < numbers.length; i++) {             System.out.println("Enter the number "+(i+1)+" : ");             numbers[i] = in.nextInt();         }         sortNumbers(numbers);     }     static void sortNumbers(int[] numbers){         for (int i = 0; i < numbers.length; i++) {             int newValue;             for (int j = 0; j < numbers.length; j++) {                 if (numbers[i] < numbers[j]) {                     newValue = numbers[j];                     numbers[j] = numbers[i];                     numbers[i]…

Record the mobile screens through MyMobiler

Dedicate to all android developers, MyMobiler is very useful for android app developers.

Features:

Records the mobile screens.
Screen Capture.
Control your mobile device from the desktop.
Transfer the file between desktop/device
USB/Wifi Connection
Supports from Android OS 2.2 version.

Download the desktop application.

Download the mobile application.

Watch the tutorials about connecting the device and desktop in YouTube: https://www.youtube.com/watch?v=t0nrGuKw1Ac