//
you're reading...
Algorithm, Java, Sorting

Heap sort code (but still bubble sort is my favorite)

It has been long since my college days that I used to hear that bubble sort is the worst sorting method and you should not use it. Theoretically its complexity was same as few others like insertion sort and selection sort that is O(n2) . But when you run it on machines and compute time for sorting it proves to be costlier.I understand. However it is probably the first sorting algorithm that we read and it welcomes us into this whole data structures world which is full of different kinds of list straight , circular, doubly, different kinds of trees,forest ,dense forest, balanced tress , unbalanced trees, red black tree, yellow green tree,graphs,sub graphs.shortest path algorithm,longest path algorithm…….the list would not end.
So, I guess bubble sort deserves quite a amount of respect which I realized even more when I wrote the code for heap sort(which I found very complex). there is nothing wrong in saying that bubble sort is your favorite(particularly in any interview where when asked to sort a list by any method , it is considered very bad when implemented using bubble sort)
I would copy the code of heap sort here(which I actually should not , because sometimes when you study any algorithm and think you understood it completely, few little things are only realized while write the code for it). However there are times you just need working code.So here goes the java class for heap sort.

import java.util.Random;

public class HeapSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] input = new int[10];

		Random generator = new Random();
		for (int i = 0; i < input.length; i++) {
			input[i] = generator.nextInt(50);
		}

		System.out.println("Initial unsorted array");

		printArray(input);

		heapify(input);

		heapsort(input);

		System.out.println("");
		System.out.println("Sorted Array after the heap sort");

		printArray(input);

	}

	public static void heapify(int[] inputArray)
	{

		for(int i=1;i		{
			shiftUp(inputArray,i,((i+1)/2)-1);

		}
		System.out.println("");
		System.out.println("AFter first heapification");

		printArray(inputArray);
	}

	/**
	 * heap sort method which calls the swap function to adjust the aray after each swap of first
	 * and last element
	 * @param input
	 */
	public static void heapsort(int[] input)
	{

		for(int i=0;i end)
		{
			return;
		}

		else if((2*start)+1 == end)
		{

			if(input[start]			{
				int k = input[start];
				input[start]=input[(2*start)+1];
				input[(2*start)+1]=k;

			//	System.out.println("swappingmid: elemnt "+start +" end :"+end +"element: "+input[start]+" and "+input[(2*start)+1]);
				swapOn(input,(2*start)+1,end);
			}
			return;
		}

		else
		{
			if(input[start]			{
				if(input[(2*start)+1]=0 && parent >=0 &&array[child]>array[parent])
		{
			int k = array[child];
			array[child]=array[parent];
			array[parent]=k;
			int x=((parent+1)/2)-1;
			shiftUp(array, parent, x);
		}
		else
		{
			return;
		}

	}

	/**
	 * prints the array
	 * @param input
	 */

	public static void printArray(int[] input)
	{
		for(int i=0;i		{
			System.out.print(input[i]+",");
		}
	}

}

I have tested it few times , but yes if you find it not working well just let me know , may be I would fix it again.
Thanks
Gaurav

Advertisements

About Gaurav Mutreja

Well I think a lot !! Now I would like to speak a bit!

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: