Home > Uncategorized > Why heapsort is unstable sort

Why heapsort is unstable sort

A sort is unstable when it does not preserve the order of same valued input in the resultant output.

Unstable sort example : Input (3a , 3b) but output (3b,3a) here 3 is the value and a,b are used to denote the order of value 3.

Now Lets see why heapsort is instable.

When sorting (in ascending order) heapsort first peaks the largest element and put it in the last of the list. So, the element that have been picked first, stays last and the element that have been picked second stays to the second last element in the sorted list.

Again, Build-Max-Heap procedure works such that it preserve the order of same value (ex:3a,3b)  in building the heap tree. For extracting the maximum element it also works from the root and try to preserve the structure of the tree (except the change for Heapify).

So, what happens, for elements with same value [3a,3b] heapsort picks 3a before 3b but puts 3a to the right of 3b. So,  As the list is sorted in ascending order we get 3b before 3a in the list .

If you try heapsort with (3a,3b,3b) then you can visualize the situation.

Hope it may helped you… 🙂

Prosunjit Biswas

UTSA.

Advertisements
Categories: Uncategorized
  1. September 23, 2012 at 3:48 am

    Thank for this tutorial.

  2. Jayesh Panchal
    May 10, 2013 at 4:44 pm

    Nice Information

    Check out my version of Heap Sort here
    http://msumca2012.blogspot.in/2013/05/heap-sort-program-in-c.html

  1. No trackbacks 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: