Heap Sortiranje opadajuci niz?imam ovaj code koji sam pripemio da sortiram neke brojeve, nebitno to on meni sortira od najmanjeg ka najvecem
kako ovde da se prepravi da sortira od veceg ka manjem.
Citao sam knjigu nigdje nisam uspio da nadjem da postoji takvosortiranje niza. ako moze da mi neko popravi ovo ili popravi
hvala punooo ekipa
Code:
void ContainerImpl::heapsort( Key * a, int n )const
{
buildheap( a, n );
while( n > 1 )
{
n--;
Key t = a[ 0 ];
a[ 0 ] = a[ n ];
a[ n ] = t;
downheap( a, 0, n );
}
}
void ContainerImpl::buildheap( Key * a, int n )const
{
for( int v = n / 2 - 1; v >= 0; v-- ) // < >
downheap( a, v, n );
}
void ContainerImpl::downheap( Key * a, int v, int n )const
{
int w = 2 * v + 1; // < erster Nachfolger von v >
while( w < n )
{
if( w + 1 < n ) // <gibt es einen zweiten Nachfolger?>
if( a[ w + 1 ] > a[ w ] )
w++; // <w ist der Nachfolger von v mit
// maximaler Markierung>
if( a[ v ] > a[ w ] || a[ v ] == a[ w ] )
return; // v hat die Heap-Eigenschaft
Key t = a[ v ];
a[ v ] = a[ w ];
a[ w ] = t; // vertausche Markierungen von v und w
v = w; // fahre mit v=w fort
w = 2 * v + 1;
}
}
void ContainerImpl::heapsort( Key * a, int n )const
{
buildheap( a, n );
while( n > 1 )
{
n--;
Key t = a[ 0 ];
a[ 0 ] = a[ n ];
a[ n ] = t;
downheap( a, 0, n );
}
}
void ContainerImpl::buildheap( Key * a, int n )const
{
for( int v = n / 2 - 1; v >= 0; v-- ) // < >
downheap( a, v, n );
}
void ContainerImpl::downheap( Key * a, int v, int n )const
{
int w = 2 * v + 1; // < erster Nachfolger von v >
while( w < n )
{
if( w + 1 < n ) // <gibt es einen zweiten Nachfolger?>
if( a[ w + 1 ] > a[ w ] )
w++; // <w ist der Nachfolger von v mit
// maximaler Markierung>
if( a[ v ] > a[ w ] || a[ v ] == a[ w ] )
return; // v hat die Heap-Eigenschaft
Key t = a[ v ];
a[ v ] = a[ w ];
a[ w ] = t; // vertausche Markierungen von v und w
v = w; // fahre mit v=w fort
w = 2 * v + 1;
}
}
