Heap Sort

-Given an orderable list of N items in A, we first insert them in a complete binary tree
and make it a heap.
- Next, we swap the first and last items, thereby putting the largest item into position N,
where it belongs.
- We then reheap the tree in positions 1 through N-1.We repeat this swap-and-reheap
process until the items in positions 1 through N of the tree are sorted. Finally, we retrive
the items back into A.

PROGRAM WRITTEN IN C++ FOR BUBBLE SORT

#include<iostream.h>
#include<string.h>
#include<conio.h>

void heap( int A[], int n);

main()
{
clrscr();
int A[20],n,no;
cout << " Input n: " ;
cin >> n;
cout << "\n Input number : ";
for(int i=0;i<n;i++)
{ cin >>no;
A[i]=no;
}
cout << "\n Sorted order : \n";
heap(A,n);
getch();
return 0;

}

void heap( int A[], int n)
{ int i,elt,s,f,ivalue,iteration=0;

// perprocessing phase; create initial heap

for (i=1; i<n ; i++)
{ elt = A[i];

// pqinsert(x,i,elt)

s=i;
f=(s-1)/2;

while(s>0 && A[f] < elt)
{
   A[s]=A[f];
   s=f;
   f=(s-1)/2;
} //end while
A[s]=elt;

} //end for

// selection phase ; repeatedly remove A[0], insert it
// in its proper position and adjust the heap

for (i=n-1; i>0 ; i--)
{ iteration++;

// pqmaxdelete(A, i+1)

ivalue = A[i];
A[i]=A[0];
f=0;

// s = largeson (0, i-1)

if(i==1)
s=-1;
else
s=1;

if(i>2 && A[2] > A[1])
s=2;

while(s>=0 && ivalue < A[s])

{ A[f]=A[s];
f=s;

// s = largeson(f, i-1)

s=2*f+1;

if(s+1 <= i-1 && A[s] < A[s+1])
s=s+1;

if(s>i-1)
s=-1;

} // end while

A[f]=ivalue;

cout << " ";
for (int j=0;j<n;j++)
cout << A[j] <<' ';
cout << '\n';

} // end for

cout << "\n No of iteration : " << iteration ;
} // end heap

Heap Sort

HEAP SORT ANIMATION PAGE

STATIC SORT FOR HEAP SORT

PROGRAM WRITTEN IN C++ FOR BUBBLE SORT