Page 248 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

k = list[i]; Notes
flag = true;
j = 2 * i;
while(j <= n && flag)
{
if((j < n) && (list[j] < list[j+ 1]))
j = j + 1 ;
if(k >= list[j])
flag = false;
else
{
list[j div 2] = list[j];
j = j * 2;
}
}
list[j div 2] = k;
}
void build_initial_heap(list x, int n)
{
int i;
for(i = n div 2; i >= 1; i--)
adjust(x, i, n);
}
void heapsort(list x, int n)
{
int i;
build_initial_heap(x, n);
for(i = n-l; i >= 1; i--)
{
exchange(list[1], list[i+1]);
adjust(x, l, i);
}
}
void exchange(int &a, int &b)
{
int t;
t = *a;
*a = *b;
*b = t;
}

LOVELY PROFESSIONAL UNIVERSITY 243