CopyPastehas never been so tasty!

Heap Sort in C#

by anonymous

  • 0
  • 0
  • 0
82 views

Orignal Source:http://codingvilla.com/heap-sort-in-csharp-single-article-625.aspx

Before proceeding towards heap sort, we must be familiar with the process “Heap”.

 

Heap

 

Heap is a binary tree that is implemented as an array. To perform heap Sort We go through from left to right across each row, however last row may not be completely filled. In heap sort one condition must be satisfied that the parent node must be greater or equal than its child node.

 

For Example, we have an array

 

100      90        80        30        60        50        70

 


Then its heap will be  

 

 

 

                                 

 

 

This procedure works on the basis of the following properties

 

The index of its parent = i / 2

 

Index of left child = 2 * i

 

Index of right child = 2 * i + 1             

 

 

                                                                                                                                               

Heap Sort

 

Heap sort is the fastest sorting algorithm just as quick sort. It’s complexity is also O(n log n).

 

How heap Sort works

 

Heap sort takes an unsorted array and first convert it into heap from the given data. It takes another array to place sorted elements. Then it removes the largest element and places it in sorted array. It then reconstructs the heap according to its properties and remove the next largest element and places it in sorted array. This process continues until all the items transfer from heap into sorted array.

 

Algorithm for Heap Sort

 

public static void HeapSort(int[] array, int arr_ubound)

        {

int i, j;

intLChild, RChild, Pnode, 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])

Pnode = RChild;

else

Pnode = LChild;

                }

else{

if(RChild>arr_ubound)

Pnode = LChild;

else

Pnode = RChild;

                }

 

if (array[i] < array[Pnode])

                {

temp = array[i];

array[i] = array[Pnode];

array[Pnode] = temp;

                }

              }

            }

temp = array[0];

array[0] = array[arr_ubound];

array[arr_ubound] = temp;

return;

            }

 

 

First we have selected the root node by the formula then left and right child are selected. If condition that if the value of child is greater than its parent node than it swaps the parent node with child. After creating heap condition it removes the largest element and places in the newly created array for sorted elements.

 

The complete example of Heap sort is illustrated with the user input in the following sample code.

 

 

Code

 

class Program

    {

static void Main(string[] args)

        {

int i;

int[] unsortedarray = {100,90,80,30,60,50,70};

 

Console.WriteLine("\n  Unsorted Array\n\n");

for (i = 0; i <unsortedarray.Length; i++)

Console.WriteLine(" " + unsortedarray[i]);

 

for (i = unsortedarray.Length; i > 1; i--)

             {

Program.HeapSort(unsortedarray, i - 1);

            }

Console.WriteLine("\n  Sorted array\n");

for (i = 0; i <unsortedarray.Length; i++)

Console.WriteLine(" " + unsortedarray[i]);

Console.ReadLine();

                    }

 

public static void HeapSort(int[] array, int arr_ubound)

        {

int i, j;

intLChild, RChild, Pnode, 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])

Pnode = RChild;

else

Pnode = LChild;

                }

else{

if(RChild>arr_ubound)

Pnode = LChild;

else

Pnode = RChild;

                }

 

if (array[i] < array[Pnode])

                {

temp = array[i];

array[i] = array[Pnode];

array[Pnode] = temp;

                }

              }

            }

temp = array[0];

array[0] = array[arr_ubound];

array[arr_ubound] = temp;

            return;

Add A Comment: